JNTU
JNTU B.Tech III FORMAL LANGUAGES AND AUTOMATA THEORY Previous Question Paper (February - 2022 - R18)
Answer any five questions. All questions carry equal marks.
Main
Design a FA for the Language which accepts odd number of 0’s and odd number of 1’s over input alphabet Σ = {0,1}.
Answer
To accept strings with an odd number of 0s and an odd number of 1s over Σ = {0, 1}, we define a DFA with four states representing the parity of 0s and 1s: q0 (even 0s, even 1s), q1 (odd 0s, even 1s), q2 (even 0s, odd 1s), and q3 (odd 0s, odd 1s).
- Start state: q0.
- Accepting state: q3.
- Transitions:
- δ(q0, 0) = q1, δ(q0, 1) = q2
- δ(q1, 0) = q0, δ(q1, 1) = q3
- δ(q2, 0) = q3, δ(q2, 1) = q0
- δ(q3, 0) = q2, δ(q3, 1) = q1
Convert the following NFA into equivalent DFA (figure 1).
Answer
To convert an NFA to a DFA, we use the subset construction method. Let the NFA states be Q = {A, B, C} with transitions: δ(A, 0) = {A, B}, δ(A, 1) = {A}, δ(B, 1) = {C}, δ(C, 0) = {B}.
- Start state of DFA is {A}.
- For state {A}: δ({A}, 0) = {A, B}, δ({A}, 1) = {A}.
- For state {A, B}: δ({A, B}, 0) = {A, B}, δ({A, B}, 1) = {A, C}.
- For state {A, C}: δ({A, C}, 0) = {A, B}, δ({A, C}, 1) = {A}.
- The DFA states are {A}, {A, B}, and {A, C}. If C is the accepting state in the NFA, then any subset containing C (i.e., {A, C}) is an accepting state in the DFA.
Convert the following NFA with ε into equivalent NFA without ε (figure 2).
Answer
Sign in to view the complete answer paper.
Design a Moore machine to count number of b’s in a given input string with a’s and b’s.
Answer
Sign in to view the complete answer paper.
Construct the Finite Automation to accept the regular expression
Answer
Sign in to view the complete answer paper.
Find the minimum state automata for the following DFA (figure 3).
Answer
Sign in to view the complete answer paper.
Obtain a regular expression for the following FA (figure 4).
Answer
Sign in to view the complete answer paper.
Check whether the following two FSM’s are equivalent or not (figure 5).
Answer
Sign in to view the complete answer paper.
Construct the Context Free Grammar for the Language
Answer
Sign in to view the complete answer paper.
Construct the CFG for the PDA M given by the transition function δ.
Answer
Sign in to view the complete answer paper.
Design Non deterministic PDA for the language
Answer
Sign in to view the complete answer paper.
Show that the following grammar is ambiguous or not:
Answer
Sign in to view the complete answer paper.
Find the GNF equivalent to the following:
Answer
Sign in to view the complete answer paper.
Show that
Answer
Sign in to view the complete answer paper.
Give an overview of recursively enumerable language.
Answer
Sign in to view the complete answer paper.
Obtain the solution for the following post’s correspondence problem:
Answer
Sign in to view the complete answer paper.