Introduction
Automata theory forms the foundation of any competitive exam, be it be GATE or ISRO. As a result, it is critical to have a solid understanding of this subject. But don't be concerned about any of it. Ninjas are here to help, and today we'll talk about Automata theory questions.
Automata Theory
The study of abstract machines and automata, as well as the computational problems that can be solved using them, is known as automata theory. It is a theoretical computer science theory.
Questions
1. Which of the following problems are decidable?
 Is it possible for a program to produce an output?
 Is L' (the complement of L), if L is a contextfree language, also contextfree?
 Is L' a regular language in the same way that L is?

Is L' also recursive if L is a recursive language?
Answer: (c,d) 100 characters/sec, 136 characters/sec
Explanation:
(a) is an undecidable variant of the Turing Machine Halting problem.
(b) is under intersection and complement, ContextFree Languages are not closed.
(c) Regular languages complement is also regular. Then, by swapping its accepting states with its nonaccepting states, a DFA that accepts the complement of L, i.e., ∑* – L, can be obtained.
(d) Under complement, recursive languages are closed. Details can be found here.
2. Which of the following strings is in L* given the language L = {ab, aa, baa}?
 abaabaaabaa
 aaaabaaaa
 baaaaabaaaab

baaaaabaa
Answer: (a,b,d)
Explanation:
(a) "abaabaaabaa" can be partitioned as a string set consisting of ab, aa, and baa. "ab aa baa ab aa" are the partitions
(b) The string "aaaabaaaa" can be divided into three parts: ab, aa, and baa. "aa ab aa aa" are the partitions.
(c) The string "baaaabaaaab" cannot be partitioned as a combination of strings in the set "ab, aa, baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
(d) The string "baaaabaa" can be partitioned into the sets ab, aa, and baa. "baa aa ab aa" are the partitions.
3. In order to perform lexical analysis for a modern language like Java, which of the following machine models is required and sufficient?
 Finite state automata
 Deterministic pushdown automata
 Nondeterministic pushdown automata

Turing machine
Answer: (a) Finite state automata
Explanation:
The first step in the compilation is Lexical Analysis. Programs are divided into tokens in lexical analysis. Finite state automata are commonly used in lexical analyzers. Tokens are typically expressed as one of the following regular expressions:
[azAZ] provides an identifier.
[azAZ09]
* If provides the keyword if.
[+] gives you integers, right?
[09]+.
4. Which of the following pairs of words has the most expressive power?
 NonDeterministic Finite Automata (NDFA) and Deterministic Finite Automata (DFA) are two types of finite automata (NFA)
 Nondeterministic pushdown automata (NDPA) and deterministic pushdown automata (DPDA) are two types of pushdown automata.
 Singletape Turing machine (deterministic) and nondeterministic singletape Turing machine (nondeterministic)
 Turing machine with a single tape and a Turing machine with multiple tapes
Answer: (b) Nondeterministic pushdown automata (NDPA) and deterministic pushdown automata (DPDA) are two types of pushdown automata.
Explanation: DPDA cannot handle languages or grammar with ambiguity, but NDPDA can handle languages with ambiguity and any contextfree grammar.
5. Which one of the following statements is FALSE?
 Every regular language has its own minimal DFA.
 Every NFA can be converted to a PDA of the same size.
 Every contextfree language's complement is recursive.

Any nondeterministic PDA can be converted to a deterministic equivalent.
Answer: (d) Any nondeterministic PDA can be converted to a deterministic equivalent.
Explanation: Deterministic PDA cannot handle ambiguous languages or grammar, but NDPDA can handle ambiguous languages and any contextfree grammar. As a result, no nondeterministic PDA can be converted to a deterministic PDA.
6. S –> aSa bSb a b ;The language generated over the alphabet {a,b} is the set of
 They're all palindromes.
 All of the palindromes are odd in length.
 Strings with the same symbol at the start and end
 All of the palindromes are the same length.
Answer: (b) All of the palindromes are odd in length.
Explanation: Language accepts the strings a, b, aaa, bbb, aba, bab, and so on. All of these strings are palindromes of odd length.
7. Which of the following languages is described by the regular expression over the alphabet 01: (0+1)*0(0+1)*0(0+1)*
 The collection of strings that contain the substring 00.
 All strings with at most two 0s are included in this set.
 The collection of all strings with at least two 0s.

All strings that start and end with either 0 or 1 are included in this set.
Answer: (c) The collection of all strings with at least two 0s.
Explanation: The regular expression contains two 0s surrounded by (0+1)*, indicating that accepted strings must contain at least two 0s.
8. Let's pretend that L1 is a recursive language. Let L2 and L3 be recursively enumerable but not recursive languages. Which of the following statements is unlikely to be correct?
 L2 – L1 can be enumerated in a recursive manner.
 L1–L3 can be enumerated in a recursive manner.
 L2 is enumerable in a recursive manner.

L2 is enumerable in a recursive manner.
Answer: (b)
a) Always True
(Recursively enumerable  Recursive ) is
Recursively enumerable
b) Not always true
L1  L3 = L1 intersection ( Complement L3 )
L1 is recursive, L3 is recursively enumerable
but not recursive Recursively enumerable languages
are NOT closed under complement.
c) and d) Always true Recursively enumerable languages
are closed under intersection and union.
9. Let w be any string with length n equal to {0,1}*. Let L denote the set of all w's substrings. In a nondeterministic finite automaton that accepts L, what is the minimum number of states?
 n1
 n
 n+1

2n1
Answer: (c) n+1
Explanation: We need minimum n+1 states to build an NFA that accepts all substrings of a binary string. For example, the following NFA accepts all substrings of “010,” and it has four states.
10. Consider the following languages: L1={0i1j  i != j}, L2={0i1j  i = j}, L3 = {0i1j  i = 2j+1}, L4 = {0i1j  i != 2j}. Which of the statements below is correct?
 Only L2 is contextfree.
 Only L2 and L3 are contextfree.
 Only L1 and L2 are contextfree
 All are contextfree
Answer: (d) All are contextfree.
Explanation: For each of the four languages, a Pushdown Automata can be created.
11. Let S and T represent language over ={a,b} which are represented by the regular expressions (a+b*)* and (a+b)*. Which of the following statements is correct?
 ScT (S is a subset of T)
 TcS (T is a subset of S)
 S=T

SnT=Ø
Answer: (c) S=T
Explanation:
S=(a+b*)*=(a*(b*)*)*=(a*b*)*
T=(a+b)*=(a*b*)*
So, S=T
12. Let L stand for the language that the grammar S – OSO/00 generates. Which of the following statements is correct?
 L = O
 L is regular but not O
 L is contextfree but not regular

L is not contextfree
Answer: (b) L is regular but not O
Explanation: Please note that grammar itself is not regular, but language L is regular as L can be represented using regular grammar, for example, S > S00/00.
13. Which of the statements below is correct?
 A deterministic pushdown automaton can always accept a language that is contextfree.
 The union of two contextfree languages results in a contextfree language.
 The contextfree intersection of two contextfree languages
 A contextfree language's complement is a contextfree language.
Answer: (b) The union of two contextfree languages results in a contextfree language.
Explanation: The following operations are used to close contextfree languages. To put it another way, if L and P are contextfree languages and D is a regular language, then the following languages are also contextfree:
• the Kleene star L * of L
• the image Ø(L) of L under a homomorphism Ø
• the concatenation of L and P
• the union of L and P
• the intersection of L with a regular language D (L n D).
Complement, intersection, and difference do not close contextfree languages.
Why is it that a) isn't correct?
The deterministic pushdown automaton understands the deterministic contextfree language. Contextfree languages aren't all deterministic. In contrast, deterministic finite Automata, which are also a subset of nondeterministic finite automata, are in a different situation.
14. The maximum number of states in an equivalent minimized DFA for any nondeterministic finite automaton (NFA) with N states is at least?
 N^2
 2^N
 2N
 N!
Answer: (b) 2^N
Explanation: If the NFA has n states, the resulting DFA may have up to 2n states, an exponentially larger number, which sometimes makes the construction impractical for large NFAs.
15. Which of the following languages is a regular language?
 {wxwR  w,x ∈ (a+b)+}
 {wxwR  w ∈ (a+b)*, x ∈ {a,b}}
 {wwRx  w,x ∈ (a+b)+}

{wwR  w ∈ (a+b)*}
Answer: (a) {wxwR  w,x ∈ (a+b)+}
Explanation:
(a) is correct because this language can be used to create regular expressions that are
(a + b)+a + b(a + b)+b, i.e., they begin and end with the same symbol.
(b) is a contextfree deterministic language because the strings before and after 'x' are identical, so it is matched.
(c) can't be regular because wwR is done first, which necessitates comparison, which finite automata can't do.
(d) is also out of the ordinary because a comparison is required.
16. In {a, b}* let w be any string of length n. Consider the set of all strings that end with at least n a's as 'L.' In nondeterministic finite automata, what is the smallest number of states that accept 'L'?
 (n+3)
 (n+1)
 n
 2 ^ n
Answer: (b) n+1
Explanation: It's correct because the minimum number of states required for NFA to end with at least two a's is (2 + 1), implying that the regular expression will be (a + b)*aaa.
17. What is the deterministic finite automata (DFA) a minimum number of states for a string starting with ba^2 and ending with 'a' over the alphabet {a, b}?
 Ten
 Nine
 Eight

Six
Answer: (d) Six.
Explanation:
The minimum number of states required is six.
18. Consider the languages X and Y to be any two ContextSensitive languages, and the language 'R' to be any regular language. Which of the following statements is/are correct?
 R's X union is regular.
 The context of the XY intersection is important.
 Contextsensitive language is the complement of Y.

None.
Answer: (b) and (c).
Explanation: for (a) X union of R = CSL but not regular union of R = CSL As a result, it's incorrect.
for (b) The intersection of two ContextSensitive Languages equals CSL because ContextSensitive Languages are closed when they meet.
for (c) Context sensitive languages are closed under complementary, so complement of CSL = CSL.
19. Consider the following three scenarios. X, Y, and Z are the three letters that make up the alphabet. If X is decidable and Y is undecidable, then which of the following statements is correct?
 If X can be reduced to Z, then Z is decidable.
 If Z is reducible to Y, Z is undecidable.
 If Y is reducible to Z, Z is undecidable.

If Z can be reduced to Y's complement, it is decidable.
Answer: (c) If Y is reducible to Z, Z is undecidable.
Explanation: Assume you have two problems, A and B. If A is undecidable and reducible to B, then B is undecidable as well, and if B is decidable and reducible to A, then A is decidable as well.
20. Which of the following regular expressions best describes the language over {a, b} that has no consecutive b's?
 (a*baa*)(b + epsilon)
 (a + ba)*(b + epsilon)
 (a*baa*)*(b + epsilon) + a*
 (a*ba*)*(b + epsilon) + a*(b + epsilon)
Answer: (b) (a + ba)*(b + epsilon)
Explanation:
(a) is erroneous. because it is devoid of (a or epsilon).
(b) is the correct answer. because it contains (epsilon, a, b, ba, ab,.....), i.e., no two consecutive b's.
(c) is erroneous. because it lacks the letters 'ab' and 'aab.'
(d) is erroneous. Because it contains the word 'bb,' which is not permitted.
21. Which of the following is true if 'X' is a set of all languages accepted by deterministic pushdown automata (DPDA) by the final state and 'Y' is a set of all languages accepted by DPDA by an empty stack?
 X is a proper subset of Y
 X = Y
 X is the proper superset of Y

none of the above
Answer: (a) Grid Computing
Explanation: the final state set of languages accepted by DPDA is a proper superset of the languages accepted by empty stack DPDA. As a result, X is a proper superset of Y.
22. Consider the languages X and Y, which are represented by the regular expressions 0*(10*)* and (0* + 1*)*, respectively, over the alphabets 0 and 1. Which of the following statements is correct?
 X is a proper subset of Y
 X = Y
 X is the proper superset of Y

none of the above
Answer: (c) Unshielded twisted pair.
Explanation: Here,
L(X)
= 0*(10*)*
= {epsilon, 0, 1, 10, 01, 00, 11, ......}
And.
L(Y)
= (0* + 1*)*
= {epsilon, 0, 1, 10, 01, 00, 11, ....}
So, both languages are equivalent to each other.
23. Consider L={(TM)  TM stands for the Turing machine, which halts on all input, and L(TM)= L' for some undecidable language L'}. The encoding of a Turing machine as a string over the alphabet 01 is (TM), and L is?
 decidable and recursively enumerable
 decidable and recursive
 decidable and nonrecursive

undecidable and recursively enumerable
Answer: (b) decidable and recursive
Explanation: Because TM is a Turing machine that halts on all input, L(TM) is decidable, and you already know that a halting Turing machine accepts recursive language, whose complement can be recursively enumerable, which is undecidable.
As a result, L is both decidable and recursive. Option (b) is the correct answer.
24. What is the minimum number of states in NFA that accept the language L if L= {(ap)*  P is a prime number} over the alphabet a?
 Three
 Five
 Two

four
Answer: (a) Three.
Explanation: L = {(ap)*  P is a prime number}
L = (a2)* U (a3)* U (a5)* U ......
L = {epsilon, a2, a3, a4, a5, ......}
Only the string 'a' is not accepted in the above NFA. As a result, three states are required.
As a result, option (a) is the correct answer.
25. Consider the following propositions and say which of the following is true
X: Given grammar, determining whether it is regular is a definable problem.
Y: If P is regular and Q is not, then (P.Q) is nonregular by definition.
Z: The pumping lemma can be used to demonstrate that a language is regular.
 only X
 only Y
 Both X and Z

Both X and Y
Answer: (d) 8B/10B encoding
Explanation: Because you can check regular grammar with the help of some productions, X is a definable problem. As a result, this assertion is correct.
Y is incorrect; for example, if P = null and Q = anbn  n 0 then P.Q= null, which is correct.
Z is also incorrect because the Pumping lemma can show that the language is not regular but not that it is regular.
As a result, option X is correct.
Check out this article  Converting NFA to DFA
FAQs

What is automata theory?
The study of abstract machines and automata, as well as the computational problems that can be solved using them, is known as automata theory. It is a theoretical computer science theory.

What are the four different types of automata?
There are four different types of automata: A finitestate machine is a machine with a finite number of states.
 Automata that are pushed down.
 Automata with a linear bound.

A Turing machine is a type of computer.

What are some examples of automata theory in practice?
Realtime examples of automata include automatic photo printing machines, artificial card punching machines, human detection and reorganization machines, and so on.

How are automatons created?
Obviously, you must first unlock that tier, but once you have, you can research the Factory and eventually build one. It costs thirty dollars in wood, fifteen dollars in steel, and one dollar in steam. Once you've got that, you can hire Engineers and have them create an Automaton for you.

Are there any other Data Structures and Algorithms content in Coding Ninjas Studio?
Yes, you may practice coding as well as answer frequently requested interview questions in Coding Ninjas Studio. The more we practice, the more probable it is that we will land a position at our desired company.
Key Takeaways
Recommended Readings
In this article, we have extensively discussed the top automata theory questions. We hope that this blog has helped you enhance your knowledge of automata questions, and if you would like to learn more, check out our articles on Library. Do upvote our blog to help other ninjas grow. Happy Coding!