CS402 Final Term Solved MCQs

Cs402- Theory of Automata · Latest Solved MCQs from Final term Papers · 10 june,2011 · FINAL TERM · Latest Mcqs · Solved MCQS for final term

Q1.

1. The production of the form nonterminal →Λ is said to be null production. Ø
2. True Page 104
3. Ø
4. False

Q2. Consider the following GFC :

s→aa|bB,a→aa|B,B→aS|Λ

here s→aaand A→B are null productions ,while B→Λ is null able production Ø ►false page 105

Ø ►True

Q3. Which statement is true?

Ø The tape of turing machine is infinite. Ø The tape of turing machine is finite. Ø The tape of turing machine is infinite when the language is regular Ø The tape of turing machine is finite when the language is nonregular.

Q4. The production of the form nonterminal →one nonterminal is called the :

Ø Null production Ø Null able production

Ø Unit production page105

Q5. For a given input, it provides the compliment of Boolean AND output.

Ø OR box Ø AND box

Q6. ( Marks: 1 ) - Please choose one

Choose the correct statement. Ø A Mealy machine generates no language as such Ø A Moore machine generates no language as such

Ø A Mealy machine has no terminal state

Ø All of these

Q7. Let Q and R be expressed by ab*a and (ba)* respectively i.e Q={aa ,aba ,abba ……}and R={Λ,ba baba,bababa…….}..aba is the only word in Q which can make a word in R, because the words in R don,t contain the

Ø Single letter

Ø Double letter page 84

Ø String Ø Null string

Q8. It delays the transmission of signal along the wire by one step (clock pulse).

Ø OR box

Ø AND box

Q9. To describe the complement of a language, it is very important to describe the ----------- of that language over which the language is defined.

Ø String Ø Regular Expression

Ø Alphabet

Ø Word

Q10. Let L be a language defined over an alphabet ∑,then the language of strings , defined over ∑, not belonging to L denoted by LC or L. is called :

Ø Non regular language of L

Ø Complement of the language L

Q11. For the given input, it provides the Boolean OR output

Ø AND box

Ø OR box

Q12. For the given input, AND box provides the Boolean AND output.

Ø True Ø False

Q13. The current in the wire is indicated by 1 and 0 indicates the absence of the current. Ø True

Ø False

Q14. If L is a regular language ,then according to Kleene,theorem ,

there exists an :

Ø TG Ø GTG

Ø FA page77

Q15. Any language that can not be expressed by a RE is said to be regular language.

Ø True

Ø False

Q16. and r2 = ( a + b) then the language (aa + bb)(a + b) will be generated by

Ø (r1 + r2)

Ø (r2)(r1) Ø (r1)* Ø (r1)(r2)

Q17. If L1 and L2 are regular languages is/are also regular language(s).

Ø L1 + L2 Ø L1L2 Ø L1*

Q18. Let L be a language defined over an alphabet Σ, then the language of strings, defined over Σ, not belonging to L, is called Complement of the language L, denoted by Lc or L’. True

False

NO19: For a certain language L, the complement of Lc is the given language L i.e. (Lc)c = L