JNTU
JNTU B.Tech II Year FORMAL LANGUAGES AND AUTOMATA THEORY Previous Question Paper (April - 2018 - R15)
Note: This question paper contains two parts A and B. Part A is compulsory which carries 25 marks. Answer all questions in Part A. Part B consists of 5 Units. Answer any one full question from each unit.
Part A
Define NFA with ε-moves.
Answer
An NFA with ε-moves is a 5-tuple (Q, Σ, δ, q0, F) where δ is a transition function defined as δ: Q × (Σ ∪ {ε}) → 2Q. This allows the automaton to transition between states without consuming any input symbol.
Design FA to accept set of all strings over {0,1} containing 3 consecutive ones.
Answer
The DFA consists of states {q0, q1, q2, q3} where q0 is the start state and q3 is the final state. Transitions are: δ(q0, 0)=q0, δ(q0, 1)=q1, δ(q1, 0)=q0, δ(q1, 1)=q2, δ(q2, 0)=q0, δ(q2, 1)=q3, δ(q3, 0)=q3, δ(q3, 1)=q3.
Give recursive definition for Regular expression.
Answer
Sign in to view the complete answer paper.
If L1={an / n≥1} and L2= {bn / n≥1} then find L1.L2.
Answer
Sign in to view the complete answer paper.
State pumping Lemma.
Answer
Sign in to view the complete answer paper.
Perform leftmost derivation for the string aaabbabbba with respect to the Grammar S → aB | bA; A → a | aS | bAA; B → b | bS | aBB
Answer
Sign in to view the complete answer paper.
Define Turing Machine.
Answer
Sign in to view the complete answer paper.
Write about Multi tape- Turing Machine.
Answer
Sign in to view the complete answer paper.
Write about Modified PCP.
Answer
Sign in to view the complete answer paper.
Give an example of a Language that is not recursive but recursively enumerable.
Answer
Sign in to view the complete answer paper.
Part B
Convert the following NFA with ε moves to DFA shown in figure 1.
Answer
Sign in to view the complete answer paper.
Design Finite Automaton which accepts set of all strings not containing 101 as substring.
Answer
Sign in to view the complete answer paper.
Design DFA for the language all strings over {0,1} which are ending with 00.
Answer
Sign in to view the complete answer paper.
Minimize the following DFA shown in figure 2.
Answer
Sign in to view the complete answer paper.
Convert the following Finite Automata to it’s equivalent Regular Expression as shown in figure 3.
Answer
Sign in to view the complete answer paper.
Construct Finite Automata for the regular expression 0*1* (00)* 1.
Answer
Sign in to view the complete answer paper.
Construct Finite Automata for ((0+1)*00)*110.
Answer
Sign in to view the complete answer paper.
Find the right linear grammar for the following regular Expression 0*110*.
Answer
Sign in to view the complete answer paper.
Design Push Down Automata for the language L={wcwR | w ∈ (0+1)*}.
Answer
Sign in to view the complete answer paper.
Convert the following Context Free Grammar (CFG) to Chomskey Normal Form (CNF): S → AaB | aaB; A → ε; B → bbA | ε.
Answer
Sign in to view the complete answer paper.
Convert the following grammar to Chomsky Normal Form: S → aSa | bSb | a | b | aa | bb.
Answer
Sign in to view the complete answer paper.
Construct CFG for the PDA given in the problem statement.
Answer
Sign in to view the complete answer paper.
Construct the Turing machine for the language L={ anb2n | n≥1}.
Answer
Sign in to view the complete answer paper.
Write properties of recursively enumerable languages.
Answer
Sign in to view the complete answer paper.
Explain about various types of Turing Machine.
Answer
Sign in to view the complete answer paper.
Design Turing Machine for the Language L={anbncn | n≥1}.
Answer
Sign in to view the complete answer paper.
Write and explain about the Chomsky hierarchy of languages.
Answer
Sign in to view the complete answer paper.
What do you mean by Halting Problem of Turing Machine?
Answer
Sign in to view the complete answer paper.
Define P – type problem with example.
Answer
Sign in to view the complete answer paper.
Define NP – Hard problem with example.
Answer
Sign in to view the complete answer paper.