Theory of Automata and Formal Languages MCQs

Theory of Automata and Formal Languages MCQs on What does automata means, Introduction to languages, Alphabets, Strings, and Defining Languages, Kleene Star Closure, Recursive definition of languages , Regular Expression, Recursive definition of Regular Expression(RE), Method 3 (Regular Expressions) , Equivalent Regular Expressions, Method 4 (Finite Automaton), Equivalent FAs,FA corresponding to finite languages, Method 5 (Transition Graph),Examples of TGs: accepting all strings, accepting none, starting with b, not ending in b, containing aa, containing aa or bb, Generalized Transition Graphs, Nondeterminism, Kleene’s Theorem, Proof (Kleene’s Theorem Part II),Kleene’s Theorem Part III, Nondeterministic Finite Automaton (NFA)Converting an FA to an equivalent NFA, Converting an FA to an equivalent NFA,NFA with Null String, NFA and Kleene’s Theorem, NFA corresponding to Concatenation of FAs, NFA corresponding to the Closure of an FA, Memory required to recognize a language, Distinguishable strings and Indistinguishable strings, Finite Automaton with output, Moore machine, Mealy machine, Equivalent machines, Regular languages, Complement of a language, Nonregular languages, Pumping Lemma, umping Lemma version II, Pseudo theorem, Decidability, Determining whether the two languages are equivalent or not? Context Free Grammar (CFG), CFG terminologies .

Theory of Automata and Formal Languages MCQs

Theory of automata and formal Quiz

Which of these machine can accept lambda.
A. Moore
B. Mealy
C. NFA
D. None
View Answer

Answer: C

Which of these is a right formula to calculate the memory required for a machine?
A. 2n
B. 2 n+1
C. 2 n+1 -1
D. None
View Answer

Answer: C

If X, Y are strings of language L and XZϵL & YZ₲L then it’s a———- language.
A. Distinguishable
B. Un-Distinguishable
C. Both A&B
D. None
View Answer

Answer: A

Which of these is the right formula for De-Morgan’s law?.
A. (L1c U L2c)c = L1∩L2
B. (L1∩L2c)U(L1c∩L2) c
C. (L1∩L2c)c U (L1c∩L2)
D. None
View Answer

Answer: A

Machines in which the outputs are attached with transitions are known as.
A. TG
B. FA
C. NFA
D. OUTPUT machines
View Answer

Answer: D

A language that has no regular expression is known as?.
A. TG
B. FA
C. Both A&B
D. None
View Answer

Answer: D

————- is an intermediate structure between FA and TG.
A. GTG
B. NFA
C. Both A & B
D. None
View Answer

Answer: B

Automata and formal languages MCQs

A machine in which the outputs are attached with states is known as.
A. Moore machine
B. Mealy Machine
C. Both A&B
D. None
View Answer

Answer: A

If a machine takes 010 as input and produce 101 as out it will be known as?
A. Increment
B. Moore
C. Mealy
D. Compliment
View Answer

Answer: D

————– have some may be none final states?
A. FA
B. TG
C. GTG
D. All
View Answer

Answer: D

If a string has no letters then it is not known as.
A. ʎ
B. Empty string
C. Null string
D. None
View Answer

Answer: B

Which is the write expression for reverse of a string?.
A. rev(s)
B. reverse(s)
C. reverse IsI
D. None
View Answer

Answer: A

If a language contains all strings of length three which expression will represents it.
A. (a+b)(a+b)2
B. (a+b)*
C. (a+b)(a+b)(a+b)
D. None
View Answer

Answer: C

Which of the following string will not be defined by this expression (a+b)*.
A. bbba
B. aaa
C. bbb
D. None
View Answer

Answer: D

———– can have multiple start sate?.
A. GTG
B. TG
C. FA
D. Both a & b
View Answer

Answer: D

If we have multiple transitions against a single input letter, then it is known as?
A. NFA
B. DFA
C. Both a & b
D. None
View Answer

Answer: A

Concatenation of finite number of letters from the alphabet is called a.
A. Alphabets
B. Language
C. Grammar
D. None
View Answer

Answer: D

If a production is applied in the leftmost nonterminal in the working string, then it is.
A. Left Recursion
B. Polish Notation
C. CFG
D. Left derivation
View Answer

Answer: D

Read Also >> C++ MCQs Question With Answers – OOP

If a CFG has the form non-terminal one terminal or two non-terminals  Non-terminal it is known as.
A. CFG
B. CFL
C. CNF
D. None
View Answer

Answer: C

If a CFG has the form non-terminal one terminal.
A. Unit Production
B. ʎ-production
C. Null able
D. Null
View Answer

Answer: A

A production of the form. Nonterminal ʎ
A. Unit Production
B. ʎ-production
C. Null able
D. Null production
View Answer

Answer: B

Which is the right combination for polish notation?.
A. Operator-Operand-Operand
B. Operand-Operator-Operand
C. Operand-Operand-Operator
D. None
View Answer

Answer: A

If we can draw more than one tree for a grammar it will be known as.
A. Ambiguous
B. Context free
C. Both A & B
D. None
View Answer

Answer: A

Maze game is an example of which.
A. TG
B. FA
C. NFA
D. None
View Answer

Answer: C

Terminals , nonterminal and production is the terminology of
A. CFL
B. Chomsky
C. PDA
D. None
View Answer

Answer: D

If L is regular then, L generates finite no of classes is the rule of.
A. Myhill Nerode Theorem
B. Pumping Lemma
C. Both A&B
D. None
View Answer

Answer: A

If two machines will create same output they will be known as..
A. Decrement
B. Moore
C. Mealy
D. Equivalent
View Answer

Answer: D

Read Also >> Computer Graphics MCQs

2 thoughts on “Theory of Automata and Formal Languages MCQs”

Leave a Comment

Please rate