JNTU
JNTU B.Tech II FORMAL LANGUAGES AND AUTOMATA THEORY Previous Question Paper (March 2022 - R16)
Answer any five questions
All questions carry equal marks
Main
Construct a DFA accepting the set of all strings ending with ‘bb’ over Σ={a,b}.
Answer
A Deterministic Finite Automaton (DFA) accepting strings ending in 'bb' over Σ={a,b} requires three states: q0 (start state), q1 (seen one 'b'), and q2 (final state, seen 'bb').
- q0: On 'a', stay in q0. On 'b', go to q1.
- q1: On 'a', go back to q0. On 'b', go to q2.
- q2: On 'a', go to q0. On 'b', stay in q2.
The transitions are: δ(q0,a)=q0, δ(q0,b)=q1, δ(q1,a)=q0, δ(q1,b)=q2, δ(q2,a)=q0, δ(q2,b)=q2.
Briefly discuss about Finite Automata with Epsilon-Transition.
Answer
A Finite Automaton with ε-transitions (NFA-ε) is an extension of the standard NFA that allows the machine to change its state without consuming any input symbol. This is represented by the empty string ε.
Key characteristics include:
- ε-closure: For any state, the ε-closure is the set of all states reachable from it using only ε-transitions.
- Flexibility: It simplifies the construction of complex automata by allowing the concatenation of smaller machines.
- Equivalence: Every NFA-ε can be converted into an equivalent DFA or NFA without ε-transitions, proving that ε-transitions do not increase the computational power of the automaton.
Draw the transition diagram of a FA which accepts all strings of 0’s and 1’s in which the number of 0’s are odd and 1’s are even?
Answer
Sign in to view the complete answer paper.
Show that the language L = {ww | w ε {a, b}*} is not regular.
Answer
Sign in to view the complete answer paper.
Write the steps in minimization of FA.
Answer
Sign in to view the complete answer paper.
Construct finite automata for the regular expression (1*0 +10*).
Answer
Sign in to view the complete answer paper.
Design Push Down Automata for the language L={wwR | w ε (0+1)*}.
Answer
Sign in to view the complete answer paper.
Convert the following grammar into a PDA that accepts the language by empty stack: S →0S1|A, A→1A0 |S| ε
Answer
Sign in to view the complete answer paper.
Eliminate ε -productions from the grammar G given as A→ aBb | bBa, B→ aB | bB | ε
Answer
Sign in to view the complete answer paper.
Design Turing Machine which will recognize strings containing equal number of 0’s and 1’s.
Answer
Sign in to view the complete answer paper.
Convert the following grammar to Greibach Normal Form : S→ SS | 0S1 | 01
Answer
Sign in to view the complete answer paper.
Explain Decision properties of Context Free Languages.
Answer
Sign in to view the complete answer paper.
Write about the following:
Linear-Bounded Automata
Answer
Sign in to view the complete answer paper.
Recursively enumerable language
Answer
Sign in to view the complete answer paper.
Decidability of PCP.
Answer
Sign in to view the complete answer paper.
Let Σ = {0,1} and A,B be the list of 3 strings each. Verify if PCP given below has a solution or not?
| List A | List B | |
|---|---|---|
| 1 | 00 | 0 |
| 2 | 001 | 11 |
| 3 | 1000 | 011 |
Answer
Sign in to view the complete answer paper.
Construct the Regular expression of the following Finite Automata.
Answer
Sign in to view the complete answer paper.
Explain about the identity rules of Regular Expressions.
Answer
Sign in to view the complete answer paper.
Construct the CFG for the PDA M = ({q0,q1}, {0,1}, {R,Z0}, δ, q0, Z0, Φ) and δ is given by:
δ(q0,1,R)=(q0,RR)
δ(q0,0,R)=(q1,R)
δ(q1,0, Z0)=(q0, Z0)
δ(q0,ε, Z0)=(q0, ε)
δ(q1,1,R)=(q1,ε)
Answer
Sign in to view the complete answer paper.