JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech III FORMAL LANGUAGES AND AUTOMATA THEORY Previous Question Paper (September - 2021 - R18)
Answer any five questions. All questions carry equal marks.
Main
Convert the given NFA to DFA.
Answer
To convert an NFA to a DFA, use the subset construction algorithm (also known as powerset construction). The steps are as follows:
- Identify the start state of the DFA, which is the epsilon-closure of the NFA start state.
- For each DFA state (which represents a set of NFA states) and each input symbol, compute the set of reachable NFA states. This set forms a new state in the DFA.
- Repeat the process for all newly created DFA states until no new sets are generated.
- A state in the DFA is an accepting state if it contains at least one accepting state from the original NFA.
Construct a DFA to accept the binary strings consisting of even number of 0’s and odd number of 1’s.
Answer
To accept binary strings with an even number of 0s and an odd number of 1s, define four states representing the parity of 0s and 1s: q0 (even 0s, even 1s), q1 (even 0s, odd 1s), q2 (odd 0s, even 1s), and q3 (odd 0s, odd 1s).
The transitions are defined as follows:
Here, q0 is the start state, and q1 is the final state because it represents the condition of having an even number of 0s (0 is even) and an odd number of 1s.
Construct a DFA to accept the binary strings divisible by 5.
Answer
Sign in to view the complete answer paper.
Eliminate the ε-transitions of the given NFA.
Answer
Sign in to view the complete answer paper.
Prove that Regular Languages are closed under i) Reverse ii) Union.
Answer
Sign in to view the complete answer paper.
Identify the regular expression accepted by the given DFA.
Answer
Sign in to view the complete answer paper.
Prove that L={WWr | W is a binary string} is not a regular language.
Answer
Sign in to view the complete answer paper.
Construct a DFA accepting language represented by (0+1)* (00+11) (0+1)*.
Answer
Sign in to view the complete answer paper.
Construct a PDA to accept the binary strings consists of number of 0’s not equal to number of 1’s.
Answer
Sign in to view the complete answer paper.
Construct a PDA to accept the language generated by the following CFG: S→Aab, A→Aab|b.
Answer
Sign in to view the complete answer paper.
Construct a PDA to accept the following language L= {anbn | n>0}.
Answer
Sign in to view the complete answer paper.
Construct a CFG to generate the binary strings consisting the number of 0’s is equal to the twice the number of 1’s. (Example: 010, 001010).
Answer
Sign in to view the complete answer paper.
Convert the following grammar into CNF: S→aSa | bSb | a | b | aa | bb.
Answer
Sign in to view the complete answer paper.
Simplify the following CFG: S→aA|aBB, A→Aaa|ε, B→bB|bbC, C→b.
Answer
Sign in to view the complete answer paper.
Construct a Turing Machine to accept the language L = { anbncn | n≥1}. Give its state Transition table and diagram. Check the machine by tracing a suitable instance.
Answer
Sign in to view the complete answer paper.
Design a TM which subtracts two unary numbers, i.e., m-n where m≥n.
Answer
Sign in to view the complete answer paper.