Theory of Automata
Final Term
Q.

Proof(Kleene‟s Theorem Part II)

If a TG has more than
A.  

Replace the old final state with new start state

 B.  

Eliminate the old start state

 C.  

Replace the old start state with final state

 D.  

Introduce the new start state
Similar Questions
1.

If Σ== {aa, bb} , then Σ* will not contain
A.  aaabbb B.  

aabbbb

 C.  

aabbaa

 D.  

bbaabbbb
2.

Below given FA has __________ RE.
A.  

a(a+b)*

 B.  

(a(a+b)*)*

 C.  

a(a+b)*a

 D.  

a(a+b)*a + b(a+b)*b
3.

“One language can have _________ TG‟s”
A.  

Only one

 B.  

Only two

 C.  More than one D.  

Only three
4.

According to 1st part of the Kleene‟s theorem, If a language can be accepted by an FA then it can be accepted by a ________ as well.
A.  

FA

 B.  

CFG

 C.  

GTG

 D.  

TG
5. Even-palindrome is a _______ language.
A.  

Non-regular

 B.  Regular= C.  

Regular but infinite

 D.  

Regular but finite
6. If L is a regular language then, Lc is also a _____ language.
A.  

Regular

 B.  

NonJregular

 C.  

Regular but finite

 D.  

None of the given
7. Pumping lemma is generally used to prove that:
A.  

A given language is infinite

 B.  

A given language is not regular

 C.  

Whether two given regular expressions of a=regular language are equivalent or not

 D.  

None of these
8. If the FA has N states, then test the words of length less than N. If no word is accepted by this FA, then it will _________ word/words.
A.  

accept all

 B.  

accept no 

 C.  

accept some

 D.  

reject no
9.

In CFG, the symbols that can‟t be replaced by anything are called________.
A.  

Terminal 

 B.  

Non Terminal

 C.  

Production

 D.  

All of given
10. Which of the following is a regular language?
A.  

String of odd number of zeroes

 B.  

Set of all palindromes made up of 0‟s and 1‟s

 C.  

String of 0‟s whose length is a prime number

 D.  

All of these
THEORY OF AUTOMATA TOPICS