# Theory of Automata and Formal Languages MCQs

5/5 - (5 votes)

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 Quiz

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

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

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

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

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

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

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

### 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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