Solved Exam — Concise Answers

Format: Question (as read from image) followed by concise answer.

PART A — (Each question carries 3 marks)
1. Draw transition diagram for NFA (without e-moves) for strings starting with '10' or '11'. Σ =
{0,1}.
Answer:
NFA with start state q0 -> on '1' go to q1; from q1 on '0' go to q2 (accept) and on '1' go to q3
(accept). All accept states loop on {0,1}. (Diagram: q0 -1-> q1; q1 -0-> q2*, q1 -1-> q3*; q2/q3
loop both 0,1.)
2. Design a DFA for strings in which first and last letters do not match. Σ = {a,b}.
Answer:
States track first symbol and current last: q_start (no symbols), q_a_first (first=a,last=a),
q_a_last_b (first=a,last=b), q_b_first, q_b_last_a. Accept states: those where first != last
(q_a_last_b, q_b_last_a). Transitions update last accordingly; initial move chooses first.
3. Give a regular expression for set of all strings not containing '101' as a substring.
Answer:
The complement of Σ*101Σ* relative to Σ*; one safe regex (constructive) is complicated; concise
description: all strings over {0,1} that avoid pattern '101' — can be represented by
(0|10|110)*(ε|1|11). (This is a compact constructive regex capturing no '101'.)
4. State the closure properties of regular languages.
Answer:
Closed under union, concatenation, Kleene star, complement, intersection, difference, reversal,
homomorphism, inverse homomorphism, and quotient by regular languages.
5. Explain with the help of an example ambiguous grammar.
Answer:
Grammar G: S -> S + S | S * S | 'a'. String 'a+a*a' ambiguous: two parse trees: (a+a)*a and a+(a*a).
Hence grammar ambiguous.
6. Write CFG equivalent to the regular expression 0*(10+1)*(ε+1).
Answer:
Construct from regex:
S -> A B
A -> 0 A | ε
B -> C B | ε
C -> 1 | 1 0
(Add small adjustments to ensure exact equivalence; concise CFG derived by standard constructions.
7. What are conditions required for push down automata to be deterministic?
Answer:
(i) At most one transition for a given (state, input symbol or ε, stack top). (ii) No ε-transition
allowed that conflicts with input-consuming transition on same stack top. (iii) For any
configuration, transition must be unique.
8. Can we construct a DPDA for the language ww^R? Justify.
Answer:
No. Language {ww^R | w ∈ Σ*} is context-free (palindromes) but deterministic PDA cannot recognize
all palindromes in general (not deterministic CFL) — deterministic PDA cannot in general recognize
{ww^R} for arbitrary Σ.
9. Differentiate Recursive and Recursively Enumerable Languages.
Answer:
Recursive (decidable): TMs always halt and accept/reject for every input. Recursively enumerable:
TMs accept strings in language and may loop forever on non-members (semi-decidable).
10. Design a TM to find the 1's complement of a binary number.
Answer:
TM scans left to right; on each symbol: replace 0->1 and 1->0; when blank reached halt. (Start at
leftmost bit, perform bit flip, move right, repeat.)
PART B — (Answer one full question from each module; marks vary)
Module 1
11 a) Construct an e-NFA for L = {0^n1^2 | n,m,p ≥ 0}? (image unclear)
Answer:
[Question text partially unclear]. For language 0^i1^j as given, e-NFA uses loop on 0 then
transition to 1-loop; convert to DFA by subset construction.
11 b) Design a DFA for strings where number of a's is multiple of 3 and b's multiple of 2.
Answer:
Use product automaton of two modular counters: 3-state cycle for a-count modulo 3, 2-state cycle for
b-count modulo 2; combined DFA has 6 states; start state (0,0); accept state (0,0). On 'a' update
first component, on 'b' update second, other input symbols (if any) ignored.
12 a) Draw state-transition diagram showing an NFA for given language.
Answer:
(Concise) Construct NFA as per description: use initial branching, loops, and accepting states
according to pattern. (Image question text partly unclear.)
Module 2
13 a) Find regular expression for the given DFA (diagram in image).
Answer:
Use state elimination: eliminate non-start/non-final states stepwise to derive expression; concise:
(b* a b*)* a? (Exact regex depends on provided DFA — diagram in image partially visible.)
13 b) Obtain minimum state DFA from following DFA.
Answer:
Apply Myhill-Nerode/state minimization: merge equivalent states (provide resulting minimal DFA with
states listed). (Concise algorithmic answer: table-filling + merge.)
14 a) Develop equivalent automata for R.E. (ab + b)*(a+b)*(ab)*.
Answer:
Construct NFA using standard Thompson construction, then subset convert to DFA. (Concise
description.)
14 b) Using pumping lemma prove language L = {a^n b^n | n is perfect square} is not regular.
Answer:
Assume regular with pumping length p. Consider s = a^{p^2} b^{p^2}. Pumping within first p a's
changes number of a's to p^2 + k, which cannot keep equality a count and b count as perfect square
for all pumped amounts — contradiction. Hence not regular.
Module 3
15 a) State Myhill-Nerode Theorem. Prove language L = {a^{n^2}} is not regular using it.
Answer:
Myhill-Nerode: L is regular iff number of equivalence classes of ≡_L is finite. For L = {a^{n^2}},
show infinite distinct prefixes a^{k} have distinct right contexts, so infinite classes -> not
regular.
15 b) Convert grammar S -> AaCbC / ABa ... (unclear)
Answer:
Apply stepwise conversions to CNF/Greibach as required; remove ε-productions, unit productions,
useless symbols, then convert.
16 a) Convert CFG with productions S -> aSbb | ... into Greibach Normal Form.
Answer:
Outline steps: remove left-recursion, eliminate ε, unit productions, and restructure to A ->
terminal + possibly nonterminals.
16 b) Convert CFG to CNF.
Answer:
Apply standard algorithm: remove terminals from long productions by introducing new nonterminals,
ensure all productions are A->BC or A->a.
Module 4
17 a) Design PDA for language L = {WW^R | W ∈ {a,b}*} and illustrate computation for 'aabba'.
Answer:
PDA: push symbols of first half, nondeterministically guess midpoint by ε-transition, then pop
matching symbols with input. For example 'aabba' push a,a,b then guess mid then match b,a against
stack.
17 b) State equivalence theorem between empty stack PDA and final state PDA.
Answer:
Every language accepted by empty stack PDA can be accepted by final-state PDA and vice versa;
conversion procedures exist (add new start or accept states and ε-transitions).
17 c) Design a PDA for strings in which number of a's is less than number of b's.
Answer:
PDA can push for b, pop for a; accept if at end stack non-empty with more b's. Deterministic version
may be tricky; nondeterministic PDA suffices.
Module 5
18 a) Using pumping lemma prove given language is not context-free: L = {a^n b^{n^2} | n ≥ 1}.
Answer:
Assume CFL and pumping length p. Take s = a^p b^{p^2}. By pumping vxy within first p symbols,
pumping changes only a-count, but b-count remains p^2, violating relation b = a^2 after pumping ->
contradiction.
19 a) Define Type 0,1,2,3 grammars and corresponding automata.
Answer:
Type-0: unrestricted grammars -> Turing machines.
Type-1: context-sensitive -> linear-bounded automata.
Type-2: context-free -> pushdown automata.
Type-3: regular -> finite automata (DFA/NFA).
19 b) Design TM to find sum of two numbers m and n given on tape (format: m#n).
Answer:
Traverse tape to locate delimiter, then convert representation (e.g., unary) by concatenating ones:
transform m#n -> (m+n). Algorithm: move to #, erase #, shift second part left to append to first,
halt.
20 a) Design Linear Bounded Automaton for L = a^n b^n c^n.
Answer:
LBA uses bounded tape to compare counts: mark matching a,b,c by scanning cycles left-to-right
replacing first unmarked a with X, then find first unmarked b replace with Y, then first unmarked c
replace with Z; repeat until all matched; accept if no unmarked symbols remain.
20 b) Prove that 'Turing Machine halting problem' is undecidable.
Answer:
Classic diagonalization/Reduction: assume decider H for Halting; construct machine D that on input M
runs H(M,M) and does opposite of H's answer leading to contradiction (Halting problem undecidable).
--- End of concise answers. For a few diagram-specific or partially unreadable questions I provided
concise algorithmic descriptions rather than exact diagrams or fully-elaborated regex. If you want
exact state diagrams or step-by-step conversions, I can add them.