JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech III Year FORMAL LANGUAGES AND AUTOMATA THEORY Previous Question Paper (August - 2022 - R18)
Answer any five questions
All questions carry equal marks
Main
Differentiate between NFA and DFA.
Answer
| Feature | DFA | NFA |
|---|---|---|
| Definition | Deterministic Finite Automaton | Nondeterministic Finite Automaton |
| Transitions | For each state and input symbol, there is exactly one transition. | For each state and input symbol, there can be zero, one, or multiple transitions. |
| ε-transitions | Not allowed. | Allowed. |
| Processing | Only one path exists for a given input string. | Multiple paths may exist; the string is accepted if at least one path leads to an accepting state. |
| Complexity | Easier to implement in hardware/software but may require more states. | More compact representation but requires backtracking or parallel simulation. |
Construct DFA for the following language:
i) L={w|w has both an even number of 0’s and even number of 1’s }
ii) L= {w|w is in the form of ‘x01y’ for some strings x and y consisting of 0’s and 1’s}.
Answer
i) The DFA for even number of 0's and 1's requires four states representing the parity of 0's and 1's: q00 (even 0's, even 1's), q01 (even 0's, odd 1's), q10 (odd 0's, even 1's), and q11 (odd 0's, odd 1's). The start state is q00, which is also the only final state.
- δ(q00, 0) = q10, δ(q00, 1) = q01
- δ(q10, 0) = q00, δ(q10, 1) = q11
- δ(q01, 0) = q11, δ(q01, 1) = q00
- δ(q11, 0) = q01, δ(q11, 1) = q10
ii) The language L = {x01y} requires the string to contain the substring '01'. The DFA states are: q0 (start state, haven't seen '0'), q1 (seen '0'), q2 (final state, seen '01'), and q3 (dead state/trap state for '01' already found).
- δ(q0, 0) = q1, δ(q0, 1) = q0
- δ(q1, 0) = q1, δ(q1, 1) = q2
- δ(q2, 0) = q2, δ(q2, 1) = q2
In this DFA, q2 is the accepting state. Once the sequence '01' is encountered, the machine transitions to q2 and stays there regardless of subsequent inputs.
Design a Moore Machine to determine the residue mod 3, where input is treated as binary.
Answer
Sign in to view the complete answer paper.
Construct the NFA accepting the following language:
i) The set of all strings over Σ = {a,b} starting with the prefix “ab”
ii) The set of all strings over {0,1} except those containing the substring “001”.
Answer
Sign in to view the complete answer paper.
Construct the NFA for the regular expression r = ((01+10)*00)*.
Answer
Sign in to view the complete answer paper.
What are the closure properties of regular languages?
Answer
Sign in to view the complete answer paper.
State the Pumping Lemma for regular sets.
Answer
Sign in to view the complete answer paper.
Construct the regular expression for the language over the set S={0,1}
i) The set of all strings containing no three consecutive 0’s.
ii) The set of all strings in which the number of occurrences is divisible by 3.
Answer
Sign in to view the complete answer paper.
Design NFA with epsilon for the RE=(a/b)*ab and convert it into DFA and further find the minimized DFA.
Answer
Sign in to view the complete answer paper.
What do you mean by ambiguity in grammars and languages? How to eliminated ambiguity in grammars? Explain with an example.
Answer
Sign in to view the complete answer paper.
Consider the grammar ( {S,A,B}, {a,b}, P, S) that has the productions: S→bA | aB; A→bAA | aS | a; B→aBB | bS | b. Find an equivalent grammar in CNF.
Answer
Sign in to view the complete answer paper.
Construct the PDA for the following grammar: S→aAA, A→aS | bS | a
Answer
Sign in to view the complete answer paper.
Discuss the applications of Push down Automata.
Answer
Sign in to view the complete answer paper.
Explain the importance of Turing Machines and also give descriptions of various types of Turing Machines with necessary examples.
Answer
Sign in to view the complete answer paper.
Discuss briefly about decidability and undecidability problems.
Answer
Sign in to view the complete answer paper.