AUTOMATA THEORY MCQS – T4Tutorials.com

Theory of Automata MCQs
Finite Automata MCQs
Regular Languages
Context-Free Grammars (CFG)
Pushdown Automata (PDA) MCQs
- Deterministic PDA vs Non-deterministic PDA MCQs
- Relationship between PDA and context-free languages MCQs
Context-Free Languages MCQs
Turing Machines MCQs
- Turing machine as a language recognizer and transducer MCQs
Decidability and Undecidability MCQs
Computational Complexity MCQs
Advanced Topics in Automata Theory
Applications of Automata Theory MCQs

18
Score: 0
Attempted: 0/18

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

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

3. For a given input, which of the followings provides the complement of Boolean AND output?
(A) DELAY box
(B) OR box
(C) NAND box (NOT AND)
(D) AND box

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

5. If L1 and L2 are regular languages, then these can be expressed by the corresponding FAs.
(A) True
(B) False
Answer: (A) 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)

7. The language that can be expressed by any regular expression is called a regular language.
(A) True
(B) False
Answer: (A) True

8. 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 SQUARE

9. Is it true that languages are proved to be regular or non-regular using pumping lemma?
(A) True
(B) False
Answer: (A) True

10. Which of the followings is the obviously infinite language?
(A) EQUAL-EQUAL
(B) EVEN-EVEN
(C) FACTORIAL
(D) PALINDROME

11. 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

12. 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

13. “CFG” stands for _________.
(A) Context Free Graph
(B) Context Free Grammar
(C) Context Finite Graph
(D) Context Finite Grammar

14. 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

15. The part of a PDA, where the input string is placed before it is run, is called?
(A) State
(B) Transition
(C) Input Tape
(D) Output Tape

16. In non-deterministic PDA, there are more than one outgoing edges from which of the following states?
(A) READ or POP
(B) START or READ
(C) POP or REJECT
(D) PUSH or POP

17. If an effectively solvable problem has an answer 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

18. 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

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.

Finite State Automata for the language of all those string containing aa as a substring in theory of automata
Finite automata FA for the language of all those strings starting and ending with same letters in theory of automata
Finite automata for the language of all those strings starting and ending with different letters in theory of automata
finite automata for the language of all those strings having double 0 or double 1 in theory of automata
Finite automata FA for the language of all those strings starting with a and ending with a in theory of automata
Finite automata to regular expression conversion in theory of automata

AUTOMATA THEORY MCQS
By: Prof. Dr. Fazal Rehman | Last updated: April 15, 2025

Related Posts:

Leave a Comment