AUTOMATA THEORY MCQS

• Theory of Automata MCQs
• Finite Automata MCQs
  • Deterministic Finite Automata (DFA) MCQs
  • Non-deterministic Finite Automata (NFA) MCQs
  • Equivalence of DFA and NFA MCQs
  • Minimization of DFA MCQs
• Regular Languages
  • Regular Expression MCQs
  • Properties of regular languages MCQs
  • Closure properties MCQs
  • Pumping Lemma for regular languages MCQs
• Context-Free Grammars (CFG)
  • CFG MCQs
  • Parse trees and derivations MCQs
  • Ambiguity in grammars MCQs
• Pushdown Automata (PDA) MCQs
  • Deterministic PDA vs Non-deterministic PDA MCQs
  • Relationship between PDA and context-free languages MCQs
• Context-Free Languages MCQs
  • Properties of context-free languages MCQs
  • Closure properties MCQs
  • Pumping Lemma for context-free languages MCQs
• Turing Machines MCQs
  • Turing machine as a language recognizer and transducer MCQs
• Decidability and Undecidability MCQs
  • Decidable languages and problems MCQs
  • Undecidable languages and problems MCQs
  • Rice’s theorem MCQs
  • Reduction techniques MCQs
• Computational Complexity MCQs
  • Time complexity classes (P, NP, NP-complete, NP-hard) MCQs
  • Space complexity classes (PSPACE, L, NL) MCQs
  • Polynomial time reductions MCQs
• Advanced Topics in Automata Theory
  • Linear-bounded automata MCQs
  • Context-sensitive grammars and languages MCQs
  • Chomsky hierarchy MCQs
  • Introduction to quantum automata MCQs
• Applications of Automata Theory MCQs

1.Which of the following delays the transmission of signal along the wire by one step (clock pulse)?

(A). NAND box (NOT AND)

(B). AND box

(C).  OR box

(D). DELAY box

(E). None of these

Answer: (D). DELAY box

2. For the given input, which of the followings provides the Boolean OR output?

(A). NAND box (NOT AND)

(B). DELAY box

(C). AND box

(D). OR box

(E). None of these

Answer: (D). OR box

3. For a given input, which of the followings provides the compliment of Boolean AND output?

(A). DELAY box

(B). OR box

(C).  NAND box (NOT AND)

(D). AND box

(E). None of these

Answer: (C).  NAND box (NOT AND)

4. If L1 and L2 are regular languages then which of the followings is/are also regular language(s)?

(A). L1 + L2

(B). L1L2

(C). L1

(D). All of above

Answer: Answer:

5. If L1 and L2 are regular languages, then these can be expressed by the corresponding FAs.

True

False

Answer: True

6. Regular Expression for the  language of words containing even number of a’s is?

(A). (a+b)aba(a+b)

(B). a+bbaabaa

(C). (a+b)ab(a+b)

(D). (b+aba)

Answer: (D). (b+aba)

7. The language that can be expressed by any regular expression is called a  regular language.

True

False

Answer: True

(19) Which of the following languages are the examples of non-regular languages?

(A). PALINDROME and EVEN-EVEN

(B). EVEN-EVEN and PRIME

(C). PALINDROME and PRIME

(D). FACTORIAL and SQURE

Answer: (C). PALINDROME and PRIME

(21) Is it true that Languages are proved to be regular or no- regular using pumping lemma?

True

False

Answer: True

Which of the followings is the obviously infinite language?

(A). EQUAL-EQUAL

(B). EVEN-EVEN

(C). FACTORIAL

(D). PALINDROME

Answer: (D). PALINDROME

Select the most nearest to the Myhill Nerode theorem.

(A). L partitions Σinto distinct classes.

(B). If L is regular then, L generates finite number of classes.

(C). If L generates finite number of classes then L is regular.

(D). All of above

(E). None of above

Answer: (D). All of above

If we want to describe the complement of a language, then it is very important to describe the ——————- of that language over which the language is defined.

(A). Regular Expression

(B). String

(C). Word

(D). Alphabet

Answer: (D). Alphabet

“CFG” stands for _________

(A). Context Free Graph

(B). Context Free Grammar

(C). Context Finite Graph

(D). Context Finite Grammar

(E). None of above

Answer: (B). Context Free Grammar

Which of the followings states are called the halt states?

(A). ACCEPT AND START

(B). ACCEPT and READ

(C). ACCEPT and REJECT

(D). ACCEPT AND WRITE

Answer: (C). ACCEPT and REJECT

The part of an PDA, where the input string is placed before it is run, is called?

(A). State

(B). Transition

(C). Input Tape

(D). Output Tape

(E). None of above

Answer: (C). Input Tape

In non-deterministic PDA, there are more than one out going edges from the which of the following states?

(A). READ or POP

(B). START or READ

(C). POP or REJECT

(D). PUSH or POP

(E). None of above

Answer: (A). READ or POP

If an effectively solvable problem has answered in yes or no, then this solution is called ———

Which of the followings are decidable problems.

(A). The two FAs are equivalent

(B). The two regular expressions define the same language

(C). Both a and b

(D). None of given

(E). None of above

Answer: (C). Both a and b

Which one of the followings was the major problem in the earliest computers?

(A). To store the contents in the registers

(B). To load the contents from the registers

(C). To calculate the mathematical formula

(D). To show the mathematical formulae

(E). None of above

Answer: (D). To show the mathematical formulae

Topic Covered: theory of automata and formal languages mcqs, theory of automata and formal languages mcqs, theory of automata and formal languages mcqs with answersautomata theory mcqs with answers, theory of automata mcqs with answers pdf free download, language grammar and automata mcqs.