CS402 Final Term Solved MCQs with References

CS402- Theory of Automata · Solved MCQS · From Final term Papers · Feb 22,2013 · PSMD01 · FINALTERM EXAMINATION Fall 2012 CS402- Theory of Automata

If Σ = {aa, bb} , then Σ* will not contain

1. aaabbb
2. aabbbb
3. aabbaa
4. bbaabbbb

Correct answer: aaabbb

Below given FA has __________ RE.

1. a(a+b)* (Page 14)
2. (a(a+b)*)*
3. a(a+b)*a
4. a(a+b)*a + b(a+b)*b

Correct answer: a(a+b)* (Page 14)

“One language can have _________ TG‟s”.

1. Only one
2. Only two
3. More than one
4. Only three

Correct answer: More than one

Above given TG represents the language i.e.

1. EVEN-EVEN (Page 22)
2. PALINDROME
3. FACTORIAL
4. None of these

Correct answer: EVEN-EVEN (Page 22)

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.

1. FA
2. CFG
3. GTG
4. TG (Page 25)

Correct answer: TG (Page 25)

Even-palindrome is a _______ language.

1. Regular
2. Regular but infinite
3. Regular but finite

If L is a regular language then, Lc is also a _____ language.

1. Regular (Page 66)
2. Non-regular
3. Regular but finite
4. None of the given

Correct answer: Regular (Page 66)

Pumping lemma is generally used to prove that:

1. A given language is infinite
2. Whether two given regular expressions of a regular language are equivalent or not
3. None of these

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.

1. accept all
2. accept no (Page 85)
3. accept some
4. reject no

Correct answer: accept no (Page 85)

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

1. Terminal (Page 87)
2. Non-Terminal
3. Production
4. All of given

Correct answer: Terminal (Page 87)

Which of the following is a regular language?

1. Set of all palindromes made up of 0‟s and 1‟s
2. String of 0‟s whose length is a prime number
3. All of these

Which of the following pairs of regular expressions are equivalent?

1. 1(001)* and (10)*10
2. x(xx)* and (x)*x
3. X  and X*
4. X  and X* X 

Correct answer: x(xx)* and (x)*x

An alphabet of Σ is valid if

1. No letter of Σ appears in middle of any other letter
2. No letter of Σ appears at end of any other letter
3. No letter of Σ appears at start of any other letter (Page 4)
4. No letter of Σ appears at end or middle of any other letter

Correct answer: No letter of Σ appears at start of any other letter (Page 4)