NFA to DFA: Definition, Differences, Conversion, and Worked Example

STEP 1 - EXTRACT: Given Data

The question asks for definitions and a conversion. The specific NFA to be converted was not provided in the question text (the diagram or table is missing), so the worked example below uses this standard NFA:

Start state: $q_0$; Final state: $q_2$; Alphabet $\Sigma = {a, b}$; no ε-transitions.

Since the original NFA is missing, the theory below is given in full and the conversion is worked on this assumed NFA. In the exam, apply the same subset-construction steps to the NFA printed on your paper.

STEP 2 - SOLVE

1. What is an NFA?

A Non-deterministic Finite Automaton (NFA) is a finite automaton where, for a given state and input symbol, there may be zero, one, or more next states, and ε-moves (transitions without consuming input) are permitted.

Formally, $M = (Q, \Sigma, \delta, q_0, F)$ where:

A string is accepted if at least one computation path ends in a final state.

2. Difference Between NFA and DFA

Every DFA is an NFA; every NFA has an equivalent DFA.

3. NFA to DFA Conversion (Subset Construction)

• Step 1: DFA start state = $\varepsilon\text{-closure}(q_0)$.
• Step 2: For each DFA state $T$ and symbol $a$: compute $\varepsilon\text{-closure}(\text{move}(T,a))$ = a new DFA state.
• Step 3: Repeat until no new states appear.
• Step 4: A DFA state is final if it contains any NFA final state.
• Step 5: Missing transitions lead to a dead state $\emptyset$.

4. Worked Example (using the assumed NFA above)

Start state: $\varepsilon\text{-closure}(q_0) = {q_0} = A$

State $A = {q_0}$:

• On $a$: ${q_0, q_1} = B$
• On $b$: ${q_0} = A$

State $B = {q_0, q_1}$:

• On $a$: ${q_0, q_1} \cup \emptyset = {q_0, q_1} = B$
• On $b$: ${q_0} \cup {q_2} = {q_0, q_2} = C$

State $C = {q_0, q_2}$:

• On $a$: ${q_0, q_1} \cup \emptyset = {q_0, q_1} = B$
• On $b$: ${q_0} \cup \emptyset = {q_0} = A$

No new states. Final DFA Transition Table:

Start state = $A$; Final state = $C$ (since it contains the NFA final state $q_2$). This DFA accepts all strings over ${a,b}$ ending in "$ab$".

Note on Missing Data

The actual NFA diagram or table intended by the exam was not included in the question, so the worked conversion above uses the assumed NFA. The theory portions (definition, differences, algorithm) are complete and correct regardless.

Check: the transition computations are consistent ($A\to B/A$, $B\to B/C$, $C\to B/A$), and the final state is $C$, the only subset containing $q_2$.

Turing Machine for L = {a01a, a10a, a0101a}

STEP 1 - EXTRACT: Given Data

• Alphabet (Σ): ${0, 1, a}$
• Language: $L = {a01a,\ a10a,\ a0101a}$ (a finite language of exactly 3 strings)
• Tape symbols (Γ): ${0, 1, a, B}$ where $B$ = blank
• Required: definition of acceptance, TM design, transition diagram, transition table, trace of a0101a

All data is present; nothing missing.

STEP 2 - SOLVE

1. How a Turing Machine Accepts a String

A Turing Machine is a 7-tuple: $$M = (Q, \Sigma, \Gamma, \delta, q_0, B, F)$$

• $Q$: finite set of states
• $\Sigma$: input alphabet
• $\Gamma$: tape alphabet ($\Sigma \subseteq \Gamma$, includes $B$)
• $\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times {L, R}$: transition function
• $q_0$: initial state
• $B$: blank symbol
• $F \subseteq Q$: set of final (accepting) states

Acceptance process:

1. The input string $x$ is written on the tape, surrounded by blanks $B$.
2. The head starts at the leftmost symbol of $x$; machine begins in $q_0$.
3. At each step the machine reads the current cell, uses $\delta$ to write a symbol, move (L/R), and change state.
4. A string is accepted if the machine halts in a final state ($q \in F$).
5. It is rejected if it halts in a non-final state or never halts.

$$L(M) = { x \in \Sigma^* \mid q_0 x \vdash^* \alpha, q_f, \beta,\ q_f \in F}$$

2. Design Strategy

Since $L$ is finite (3 exact strings), the TM scans left-to-right, tracking progress through the shared prefix a, then branching. Since we only recognize, we write back the same symbol and move R.

States:

3. Transition Table

$\delta(\text{state},\text{read}) = (\text{write},\text{move},\text{next})$

4. Transition Diagram

             a         0          1          a         B
  ->(q0) --------> (q1) ----> (q2) ----> (q3) ----> (q8) ----> ((qa))
                     | 1              a01a path |
                     v                          | 0
                   (q4)                         v
                     | 0                       (q6)
                     v                          | 1
                   (q5)                         v
                     | a                       (q7)
                     v                          | a
                   (q9)                         v
                     | B                      (q10)
                     v                          | B
                   ((qa))                       v
                                              ((qa))

(All undefined/unexpected inputs go to $q_r$, reject.)

5. Acceptance of a0101a

Tape: $B\ a\ 0\ 1\ 0\ 1\ a\ B$

The machine halts in $q_a$ (final state), so the string a0101a is ACCEPTED. ✓

Context Free Grammar and Conversion to Chomsky Normal Form

STEP 1 - EXTRACT (Given data)

This is a theory and derivation question. The only structural data needed is the grammar chosen for the worked example, which is:

$$ \begin{aligned} S &\to ASB \mid \varepsilon\ A &\to aAS \mid a\ B &\to SbS \mid A \mid bb \end{aligned} $$

No data is missing; the question is fully answerable.

STEP 2 - SOLVE

Part 1: Context Free Grammar (CFG)

A Context Free Grammar is a 4-tuple $G = (V, T, P, S)$ where:

• $V$ = finite set of non-terminals (variables)
• $T$ = finite set of terminals, with $V \cap T = \varnothing$
• $P$ = finite set of productions of the form $A \to \alpha$, where $A \in V$ and $\alpha \in (V \cup T)^*$
• $S \in V$ = start symbol

Every production has exactly one non-terminal on the left, so it can be replaced regardless of surrounding context - hence "context free."

Example: $$S \to 0S1 \mid \varepsilon$$

• $V={S},\ T={0,1},\ S=S$
• Generates ${0^n1^n \mid n \ge 0} = {\varepsilon, 01, 0011, \dots}$

CFGs describe the syntax of programming languages and drive parser/compiler design.

Part 2: Chomsky Normal Form (CNF)

A CFG is in CNF if every production is of the form:

1. $A \to BC$ (two non-terminals), or
2. $A \to a$ (single terminal)

with the sole exception $S \to \varepsilon$ allowed if $\varepsilon$ is in the language, and $S$ must not appear on any RHS.

Conversion steps:

1. Add a new start symbol.
2. Eliminate $\varepsilon$-productions.
3. Eliminate unit productions.
4. Reduce RHS length to 2 (introduce variables).
5. Replace terminals in long productions with new variables.

Worked Example

Original grammar: $$ S \to ASB \mid \varepsilon,\quad A \to aAS \mid a,\quad B \to SbS \mid A \mid bb $$

Step 1: New start symbol $S_0$

$$ S_0 \to S,\quad S \to ASB \mid \varepsilon,\quad A \to aAS \mid a,\quad B \to SbS \mid A \mid bb $$

Step 2: Eliminate $\varepsilon$-productions

Nullable variables: $S$ (since $S\to\varepsilon$). Insert versions with $S$ deleted:

• $S \to ASB \Rightarrow S \to ASB \mid AB$
• $A \to aAS \Rightarrow A \to aAS \mid aA$
• $B \to SbS \Rightarrow B \to SbS \mid bS \mid Sb \mid b$
• $S_0 \to S$ keeps $S_0 \to \varepsilon$ (since $\varepsilon$ is in the language)

$$ \begin{aligned} S_0 &\to S \mid \varepsilon\ S &\to ASB \mid AB\ A &\to aAS \mid aA \mid a\ B &\to SbS \mid bS \mid Sb \mid b \mid A \mid bb \end{aligned} $$

Step 3: Eliminate unit productions

Unit pairs: $S_0 \to S$, $B \to A$.

• $S_0 \to S$: $S_0 \to ASB \mid AB$
• $B \to A$: $B \to aAS \mid aA \mid a$

$$ \begin{aligned} S_0 &\to ASB \mid AB \mid \varepsilon\ S &\to ASB \mid AB\ A &\to aAS \mid aA \mid a\ B &\to SbS \mid bS \mid Sb \mid b \mid aAS \mid aA \mid a \mid bb \end{aligned} $$

Step 4: Replace terminals in multi-symbol productions

Introduce $X_a \to a$, $X_b \to b$. Replace terminals wherever they sit with other symbols:

$$ \begin{aligned} S_0 &\to ASB \mid AB \mid \varepsilon\ S &\to ASB \mid AB\ A &\to X_aAS \mid X_aA \mid a\ B &\to SX_bS \mid X_bS \mid SX_b \mid b \mid X_aAS \mid X_aA \mid a \mid X_bX_b\ X_a &\to a\ X_b &\to b \end{aligned} $$

Step 5: Reduce RHS length to 2

Introduce helper variables:

• $ASB$: let $C_1 \to SB$, so $\to A C_1$
• $X_aAS$: let $C_2 \to AS$, so $\to X_a C_2$
• $SX_bS$: let $C_3 \to X_bS$, so $\to S C_3$

Final CNF grammar: $$ \begin{aligned} S_0 &\to AC_1 \mid AB \mid \varepsilon\ S &\to AC_1 \mid AB\ A &\to X_aC_2 \mid X_aA \mid a\ B &\to SC_3 \mid X_bS \mid SX_b \mid b \mid X_aC_2 \mid X_aA \mid a \mid X_bX_b\ C_1 &\to SB\ C_2 &\to AS\ C_3 &\to X_bS\ X_a &\to a,\qquad X_b \to b \end{aligned} $$

Every production is now $A \to BC$ or $A \to a$ (plus the permitted $S_0 \to \varepsilon$), so the grammar is in Chomsky Normal Form.

String, Substring, Empty String, and Empty Language over {a, b}

1. String

A string (also called a word) is a finite sequence of symbols taken from an alphabet.

Over the alphabet Σ = {a, b}, a string is any finite arrangement of the symbols a and b.

Examples over {a, b}:

• a
• b
• ab
• aab
• bba
• abab

Formally, if Σ = {a, b}, then Σ* (Kleene closure) gives the set of all possible strings over {a, b}, including the empty string:

Σ* = {ε, a, b, aa, ab, ba, bb, aaa, aab, ...}

2. Substring

A string v is called a substring of string w if v appears as a contiguous sequence of symbols within w (obtained by removing zero or more leading symbols and zero or more trailing symbols from w).

Example over {a, b}:

Let w = abab

Substrings of w include:

• a, b, ab, ba, aba, bab, abab, ε

Note: Every string is a substring of itself, and the empty string ε is a substring of every string.

3. Empty String

The empty string (denoted ε or sometimes λ) is a string that contains no symbols at all. Its length is 0.

Key properties of ε over {a, b}:

Example:

If x = ab, then ε · x = ab and x · ε = ab

The empty string acts as the identity element for string concatenation.

4. Empty Language

A language over an alphabet Σ is a set of strings, i.e., a subset of Σ*.

The empty language (denoted ∅) is a language that contains no strings at all.

Over {a, b}:

∅ = { } (a set with no members)

Important distinction:

Note: ∅ ≠ {ε}. The empty language has no strings, whereas {ε} is a language containing one string (the empty string).

The empty language ∅ is a valid language over any alphabet, including {a, b}.

Summary Table

Regular Expressions over {a, b}

Given data

• Alphabet: $\Sigma = {a, b}$
• Part (a): strings with exactly two a's AND at least two b's.
• Part (b): strings with an even number of a's, and each a immediately followed by at least one b.

Part (a): Exactly two a's and at least two b's

Structure. With exactly two a's, every string has the shape:

$$b^,a,b^,a,b^*$$

The three $b^*$ blocks (before, between, after) hold all the b's. The constraint is that the total number of b's across all three blocks is at least 2.

Deriving a compact expression. The plain shape $b^*ab^ab^$ allows 0 or 1 b's, which we must forbid. So we subtract those cases by forcing the b-count $\ge 2$. This is cleanly expressed by casing on where the "guaranteed" b's sit. A correct enumeration (each covers b-total $\ge 2$, union covers all):

$$R = b^{2+}ab^ab^ ;+; b^+ab^+ab^* ;+; b^+ab^*ab^+ ;+; b^ab^{2+}ab^ ;+; b^*ab^+ab^+ ;+; b^*ab^*ab^{2+}$$

where $b^{2+} = bbb^$ (at least two b's) and $b^+ = bb^$.

A shorter equivalent that is fully acceptable in an exam:

$$\boxed{R = b^*a,b^a,b^\ \text{restricted to total } b\text{'s} \ge 2}$$

expressed formally as the union above. In terms of "at least one block has $bb$, OR two blocks each have a $b$":

$$R = bbb^* a, b^* a, b^* + b^* a, bbb^* a, b^* + b^* a, b^* a, bbb^* + bb^* a, bb^* a, b^* + bb^* a, b^* a, bb^* + b^* a, bb^* a, bb^*$$

Check. Every accepted string must carry exactly two a's, so test $baab$: it has one b before the a's, the two a's adjacent, and one b after, giving a b-total of 2, and it matches the term $b^+ab^*ab^+$. The string $aab$ carries only one b and is correctly rejected. The string $bbaa$ has two b's ahead of the first a and matches the term $b^{2+}ab^ab^$.

Part (b): Even number of a's, each a followed by at least one b

Structure.

• Each a must be immediately followed by at least one b, so the basic unit is $ab^+$ (i.e. $abb^*$).
• The number of a's must be even, so units come in pairs: $(ab^+ab^+)$, repeated zero or more times.
• Extra b's may appear at the start (before any a).

Regular expression:

$$\boxed{R = b^,(ab^+,ab^+)^}$$

Verification:

Final Answers

(a) Exactly two a's and at least two b's: $$R = b^{2+}ab^ab^ + b^+ab^+ab^* + b^+ab^*ab^+ + b^ab^{2+}ab^ + b^*ab^+ab^+ + b^*ab^*ab^{2+}$$

(b) Even number of a's, each a followed by at least one b: $$R = b^(ab^+ab^+)^$$