Gate Theory of computation doubts.

Enter Name of Correspondence Set, Page Number, Question Number, Your Name and Roll Number for Query!

Moderator: CS Moderators Team

Gate Theory of computation doubts.

Postby jayaswalsnehil » Sun Sep 15, 2013 2:52 pm

Please tell me the explanation and answer of following questions:

1. how many 2 state Finite automata can be drawn which accepts empty language?

2. fsm with output capability can be used to add two integers in binary representation?

3. sum of regular language and Non-regular language is regular?


4. String of 0's whose length is a perfect square is regular language?

5. If R is regular and N is non-regular ,then R+N is regular?
jayaswalsnehil
 
Posts: 3
Joined: Sat Sep 14, 2013 10:30 pm
My College/Company:: Nirma university
Roll Number: 11420149

Re: Gate Theory of computation doubts.

Postby jayaswalsnehil » Wed Nov 06, 2013 2:04 pm

please answer my previous question of TOC, please
jayaswalsnehil
 
Posts: 3
Joined: Sat Sep 14, 2013 10:30 pm
My College/Company:: Nirma university
Roll Number: 11420149

Re: Gate Theory of computation doubts.

Postby BhaskarMukhoty » Thu Dec 05, 2013 10:19 pm

I will answer the last one first, and this should cover the third one also, as "sum of language" should mean union of language.

Ans to 3 and 5:

Regular languages are closed under union, intersection and complementation set operations.

Since A - B = A intersection (complement of B), regular languages are closed under set substraction operation too.


Now consider R+N to be regular.

then, So is (R+N)-R

Which implies N is regular, a contradiction.

Hence, R+N is not regular.
BhaskarMukhoty
 
Posts: 2
Joined: Thu Dec 05, 2013 9:44 pm
My College/Company:: Tech Mahindra
Roll Number: 0

Re: Gate Theory of computation doubts.

Postby BhaskarMukhoty » Thu Dec 05, 2013 10:25 pm

Ans to 4:


String of 0's whose length is perfect square, could not be regular.
This can be proved using pumping lemma for regular languages.
BhaskarMukhoty
 
Posts: 2
Joined: Thu Dec 05, 2013 9:44 pm
My College/Company:: Tech Mahindra
Roll Number: 0


Return to CS Question

Who is online

Users browsing this forum: No registered users and 1 guest