2-MARK QUESTIONS — Short, precise

answers (use 1–2 sentences each)

1. State the DFA.
A DFA is a 5-tuple M =(Q , Σ , δ , q 0 , F) where Q is a finite set of states, Σ an alphabet,
δ :Q × Σ → Qa deterministic transition function, q 0 ∈ Qthe start state and F ⊆ Q the set
of accept states.
2. List any four applications of Finite Automata.
Lexical analysis (compilers), regex/pattern matching, text search (grep), simple
protocol/state validation.
3. Define an Alphabet in automata theory.
An alphabet Σ is a finite nonempty set of symbols; strings are finite sequences of
symbols from Σ .
4. State Derivation Tree.
A derivation tree (parse tree) graphically shows how a string is derived from a
grammar: root = start symbol, internal nodes = variables, leaves = terminals.
5. Define the Concatenation Property.
Concatenation of strings x , y is xy formed by writing y after x ; for languages L1 , L2,
L1 L2={xy ∣ x ∈ L1 , y ∈ L2 }.
6. State the term 'Pumping Lemma' in one sentence.
For any infinite regular language there exists a pumping length psuch that any string s
with ∣ s ∣≥ pcan be written s= xyzwith ∣ y ∣> 0 ,∣ xy ∣ ≤ pand x yi z ∈ Lfor all i≥ 0 .
7. Define 'inherently ambiguous context-free languages'.
A CFL is inherently ambiguous if every CFG generating it is ambiguous (there is no
unambiguous grammar for it).
8. Main conditions for applying Pumping Lemma for CFLs.
Language must be context-free; select pumping length p; choose a string of length ≥
p; decomposition into uvxyz with ∣ vy ∣>0 , ∣ vxy ∣ ≤ p ; pumping v , y gives strings in the
language if CFL.
9. Name one context-free language.
n n
{a b ∣n ≥ 0 }.
10. Write only the types of Turing Machines.
Deterministic, nondeterministic, multitape, multitape nondeterministic, 2-way,
universal Turing machine, linear bounded automaton (restricted TM variant).
11. Define Finite State System.
A system modeled by a finite state machine: finite states and transitions reacting to
inputs; used for modeling control logic.
12. Describe Deterministic Finite State Systems.
Each state and input pair has exactly one next state (no choices); behavior fully
determined by current state and input.
13. State DFA.
(Repeated) See Q1.
14. Write use of Pumping Lemma.
To prove a language is not regular (or not context-free, using CFL pumping lemma
variant).
 15. State Regular Language.
A language recognized by some finite automaton (DFA/NFA) or described by a
regular expression.
16. Full form of CNF.
Chomsky Normal Form.
17. Two main types of production rules of CNF.
A → BC (two nonterminals) and A → a(single terminal); optionally start symbol S → ϵ .
18. Define Left Recursion in CFG.
A nonterminal A is left-recursive if A ⇒+ ¿ Aα ¿ for some string α , i.e., a production
A → Aβ .
19. Full form of PDA.
Pushdown Automaton.
20. Define term 'Turing Machine'.
An abstract machine with infinite tape, head that reads/writes and moves, and finite
control; used to model computation.
21. Recognize 'transition' in Finite Automata.
A mapping from (state, input) to next state; in DFA unique, in NFA may be multiple
or ε.
22. Define Non-deterministic finite state systems.
NFAs allow multiple possible next states for a given state and input (or ε-moves).
23. State Initial state in a Finite State System.
The designated start state q 0from which computation begins.
24. Write component of CFG.
A CFG is a 4-tuple (V , Σ , R , S ): variables V , terminals Σ , productions R , start
symbol S.
25. List two closure properties of regular sets.
Closed under union and concatenation (also Kleene star, intersection with regular).
26. Full form of GNF.
Greibach Normal Form.
27. Meaning of ε-Production.
A production of the form A → ϵ that allows a nonterminal to derive the empty string.
28. Define CYK — Algorithm.
Cocke–Younger–Kasami algorithm: dynamic programming method to decide
membership of a string in a CNF grammar in O(n 3 ∣G ∣).
29. State role of 'stack' in PDA.
Provides unbounded LIFO memory used to store intermediate symbols (for counting,
nested structures) enabling recognition of CFLs.
30. List two components of the Turing Machine.
Finite control (state set) and infinite tape with read/write head.

7–8-MARK QUESTIONS — Detailed

answers with sketchable diagrams
I’ll answer the most likely 7–8 mark items seen in your picture. For each, I include a diagram
description that you can draw during the exam.
1. Analyze a DFA that accepts all strings ending in ‘ax’ and draw the
transition table.

Idea: The DFA needs to track the last two characters; accept iff suffix = “ax”.

States (minimal):

 q 0: no relevant suffix yet (start).

 q a: last symbol seen was ‘a’.
 q ax : last two symbols were “ax” (accepting).

(Optionally a dead/sink state if alphabet has other symbols, but not necessary — you can
route to q 0.)

Transitions (alphabet Σ={a , x }— extend similar for other symbols):

 From q 0: on a → q a; on x → q 0.
 From q a: on x → q ax ; on a → q a(still last symbol a).
 From q ax : on a → q a(last symbol becomes a); on x → q 0(last two: …x x → not ax).

Transition table (concise):

State on a on x
q0 qa q0
qa qa qax
qax (*) qa q0

(*) accepting state

Sketch: Draw three circles q0 → q_a (label 'a'), q_a → q_ax (label 'x'), loops for appropriate
transitions. Mark q_ax as double circle.

Why correct: The DFA always keeps track of the last one or two characters so when input
ends it can decide whether the last two were 'a' then 'x'.

2. Show a language is not regular using Pumping Lemma (example L={an bn }).

Proof (standard):

1. Assume Lis regular; let pumping length be p.

2. Choose string s=a p b p ∈ Lwith ∣ s ∣≥ p.
3. By pumping lemma, s= xyzwith ∣ xy ∣≤ p and ∣ y ∣> 0. So y consists only of a s (within
the first ppositions).
4. Pump i=0 : xz=a p−∣ y ∣ b pwhich has fewer a s than b s → not in L.
 5. Contradiction because pumping lemma requires xz ∈ L. Thus Lis not regular.

Key point to write: Emphasize selection of s and that y lies entirely in the a block.

3. Analyze a DFA that accepts all binary strings ending in ‘01’ and draw
transition table.

States:

 q 0: start, no suffix yet.

 q 0 a/q 0 analog: track last symbol.
 Simpler states: q 0(start/last read not relevant), q 1(last symbol was 0), q 01(last two are
01 — accepting).

Transitions (Σ={0,1}):

 q 0: on 0→q 1; on 1→q 0.
 q 1: on 0→q 1 (last is 0), on 1→q 01.
 q 01: on 0→q 1; on 1→q 0.

Table similar to earlier; draw 3 states with arrows labeled.

4. Describe Pumping Lemma (with block diagram).

Statement: For any regular language Lthere exists pumping length psuch that any string
s ∈ Lwith ∣ s ∣≥ pcan be divided s= xyzwith ∣ xy ∣≤ p ,∣ y ∣>0, and x yi z ∈ Lfor all i≥ 0 .

Block-diagram you can draw:

A horizontal string sdivided into three sections |x| |y| |z| with constraint ∣ xy ∣≤ p . Indicate that
y can be repeated/pumped producing x y 0 z , x y 2 z , ….

Use: Prove non-regularity by showing pumping fails for a chosen string.

5. Analyze differences between deterministic and non-deterministic Turing

Machines with examples.

Deterministic TM (DTM):

 For each state and tape symbol there is at most one transition.
 Computation is a single sequence of configurations.
 Model for standard computation; equivalent in language recognition to NTM for
decidability.

Non-deterministic TM (NTM):
  Can have multiple possible transitions from a state/symbol.
 Computation branches into many paths — accepts if any branch accepts.
 Useful for complexity theory (e.g., nondet polynomial time = NP).

Example difference: For a DTM you must specify an explicit head move/write for each
case; an NTM can "guess" a position by branching and later verify.

Important remark: In terms of language recognition (decidable languages) both are

equivalent (DTM can simulate NTM), though possibly with exponential slowdown.

6. Compare the use of Turing Machines in recognizing context-free and

context-sensitive languages.

 CFG (CFL) recognition can be done by nondeterministic PDA (for CFLs) or by

Turing machines; PDAs are simpler.
 Context-sensitive languages require more power — linear bounded automata (LBA,
a TM with tape limited to input length) recognize CSLs.
 TMs can simulate both: TM is the most powerful of these models, able to
decide/recognize recursively enumerable languages; CFLs and CSLs are subsets of
TM-recognizable languages.

7. Short notes (remove useless symbols, eliminate ε productions, remove unit

productions).

 Removing useless symbols: Remove nonterminals that never derive a terminal string
(non-generating) and those not reachable from start.
 Eliminating ε-productions: For each nullable variable, remove occurrences and add
productions for combinations; keep start → ε only if language contains ε.
 Removing unit productions: Replace unit rules A → B by copying productions of B
into A until no unit rules remain.

8. Analyze relationship between CFG and PDA.

 For every CFG there exists a PDA that recognizes the same language (construct by
simulating leftmost derivations using stack).
 For every PDA there is a CFG that generates the same language (more involved; PDA
to CFG conversion).
 Hence CFGs and PDAs characterize exactly the class of context-free languages.

9. Analyze a DFA that accepts all binary strings ending in 'ab' and draw
transition table.
Same as earlier patterns — track last two symbols using 3 states: start, saw 'a', accept (saw
'ab') — define transitions accordingly.

10. Discuss the statement of Pumping Lemma for Regular Languages.

Explain lemma precisely and illustrate proof technique for nonregularity with a worked
example (e.g., a n b n).

11. Discuss significance of Chomsky hierarchy and relation with Turing

Machines.

Chomsky hierarchy: Type-0 (recursively enumerable) ⊇ Type-1 (context-sensitive) ⊇

Type-2 (context-free) ⊇ Type-3 (regular).


 Turing machines characterize Type-0 (and via restrictions LBAs characterize Type-1).
 Shows increasing language expressive power and required machine power.

12. Create a Turing Machine that recognizes palindromes and explain

transitions.

Idea (high level):

 Mark leftmost symbol (replace with X), move right to find rightmost unmarked
symbol, compare; if match, mark it with X and return to left; repeat until all marked
or single unmarked symbol remains; accept. If mismatch, reject.

Sketch transitions:

 State q start : if read a → write X, move R, go to searchR_a; if read b → write X, move

R, go to searchR_b; if blank → accept.
 In searchR_a: move right skipping X until you find rightmost unmarked symbol; if it's
a, replace with X and move to returnLeft; if b or blank → reject.
 ReturnLeft: move left to next unmarked leftmost; go to q start and repeat.

Explain correctness: Each round removes two matching outer symbols; if all match, accept.

10-MARK QUESTIONS — Full solutions

(construction, table, correctness)
I’ll answer the main 10-mark questions visible in your images.
1. Construct a DFA that accepts all strings that start with 0 over {0,1} — give
transition diagram and table.

Objective: Accept strings whose first symbol is 0 (including single 0), reject those that start
with 1 or empty string (if exam expects starting with 0 explicitly).

States:

 q 0— start (no symbol read yet).

 q acc — accepting: first symbol was 0 (and we accept all continuations).
 q rej— rejecting sink: first symbol was 1 (and remain rejecting).

Transition function:

 δ (q 0 ,0)=qacc
 δ (q 0 ,1)=q rej
 δ (q acc , 0)=qacc
 δ (q acc , 1)=q acc
 δ (q rej , 0)=q rej
 δ (q rej , 1)=qrej

Transition table:

State on 0 on 1
q0 qacc qrej
qacc(*) qacc qacc
qrej qrej qrej

(¿ accept)

Diagram: 3 circles; arrow from start to qacc labeled 0 and to qrej labeled 1; loop on qacc for
both 0/1; qrej loops on both. Mark qacc double circle.

Edge cases:

 Empty string: rejected (no first symbol) — explain if the question considers empty
string: if empty should be rejected unless specified otherwise.

Correctness: The DFA accepts iff first symbol read was 0 because after the first input it
either goes to qacc or qrej and then remains in that status.

2. Interpret the Two-Way Finite Automaton (2DFA).

Definition: A 2DFA is like a DFA but its read head can move left or right on the input tape
(not just strictly right). It still has a finite control.

Properties:

 2DFAs still recognize exactly the regular languages (no extra expressive power), but
can be more succinct for some languages and allow algorithms that reexamine input.
 Formal transition: δ :Q ×(Σ ∪{▹ , ◃ })→ Q× {L , R }.

Example use: Recognize whether first and last symbols are equal by moving to end and back
— doable with 2DFA (and also with DFA by tracking last symbol in a single pass if alphabet
finite).

Sketch to draw: small tape with left and right moves and control state.

3. Summarize finite automata with output and difference between Mealy and
Moore machines.

Finite automata with output: Extend automata to produce outputs as they process input.

 Moore machine: output associated with states. M =(Q , Σ , Γ , δ , q 0 , λ)where λ :Q → Γ

. Output depends only on current state (so one extra output symbol is often produced
at start).
 Mealy machine: output associated with transitions. λ :Q × Σ → Γ . Output depends on
state and input, often producing outputs sooner (no extra start output).

Difference: Mealy outputs on transitions (finer control, often fewer states); Moore outputs on
states (simpler conceptual model, delayed output by one step).

Conversion: Every Mealy machine can be converted to an equivalent Moore machine and
vice versa (may require more states).

4. Evaluate and justify DFA and NFA equivalence with example and
explanation.

Claim: DFAs and NFAs recognize exactly the same class of languages (regular languages).

Proof idea (subset construction):

 Convert an NFA N=(Q , Σ , δ ,q 0 , F )to a DFA D whose states are subsets of Q . Start
state = ϵ -closure({q0 }). For each subset Sand input a , transition to ϵ -closure(
¿ q ∈ S ❑ δ(q , a)). Accepting subsets are those with at least one NFA accepting state.
This DFA simulates all NFA branches deterministically.
Example: NFA for (a|b)*abb can be converted to DFA by subset construction; show small
example quickly.

Complexity remark: NFA may be exponentially smaller than equivalent DFA in worst case.

5. Assume a string that is starting with ‘k’ for DFA like k ={k , kk , kb , kn , rm}.
Design a transition diagram for the given state of string using a tuple of DFA
and the mechanism of DFA.

This question wording is a bit odd in the images. Interpreting as: design a DFA that accepts
strings starting with a particular symbol k (or prefix set). Here’s how to answer:

Interpretation A (strings starting with letter 'k'): Use the construction in Q1 (start symbol
must be 'k' instead of 0). States: q 0(start) → on 'k' go to q acc , else to q rej.

Interpretation B (accept specific set of short words {k , kk , kb , kn , rm} ): Build a DFA that
accepts exactly those finite strings — create a prefix tree (trie) and convert leaves to accept
states; remaining transitions to sink.

Mechanism (formal tuple): M =(Q , Σ , δ , q 0 , F) where Q = nodes of trie plus sink. Define δ
per trie edges; undefined transitions → sink. F = leaf nodes representing accepted words.

Sketch: Draw trie: root —k→ state1 —k→ accept (kk) etc; root —r→ … for rm.

Explain correctness: DFA accepts only words in the set by definition of trie.

6. Evaluate the power of PDA in recognizing context-free languages.

Answer (comprehensive):

 PDAs are strictly more powerful than finite automata but less powerful than full
Turing machines.
 PDAs recognize exactly the context-free languages (CFLs). Deterministic PDAs
recognize a strict subset (deterministic CFLs).
 Example: L={an bn }— not regular but a PDA can recognize by pushing an A for each
a and popping for each b .
 PDAs cannot recognize all context-sensitive languages (e.g., {an bn c n } is not CFL).

Describe PDA operation (for a n b n):

 Start: push bottom marker.

 For each a : push A .
 On first b : switch to pop mode; for each b pop one A .
 If stack returns to bottom exactly at input end → accept