BSc CSIT (TU) Science Theory of Computation (BSc CSIT, CSC257) Question Paper 2074 Nepal

Finite Automata

A Finite Automaton (FA) is an abstract mathematical model of a machine with a finite amount of memory used to recognize regular languages. Formally, a Deterministic Finite Automaton (DFA) is a 5-tuple:

where:

• $Q$ = finite set of states
• $\Sigma$ = finite input alphabet
• $\delta : Q \times \Sigma \to Q$ = transition function
• $q_0 \in Q$ = start state
• $F \subseteq Q$ = set of accepting (final) states

DFA for even number of 0's and even number of 1's

We track parity of 0's and parity of 1's. There are four combinations, giving four states:

• $A$ = (even 0's, even 1's) — start and accepting
• $B$ = (odd 0's, even 1's)
• $C$ = (even 0's, odd 1's)
• $D$ = (odd 0's, odd 1's)

Reading a 0 flips the 0-parity; reading a 1 flips the 1-parity.

Transition Table

($\to$ = start state, $*$ = final state). $F = \{A\}$.

Transition Diagram (described)

Four states $A, B, C, D$ arranged as a square. Horizontal edges (labelled 0) connect $A\leftrightarrow B$ and $C\leftrightarrow D$ (toggling 0-parity). Vertical edges (labelled 1) connect $A\leftrightarrow C$ and $B\leftrightarrow D$ (toggling 1-parity). $A$ has an incoming start arrow and is drawn with a double circle (accepting).

Example: string 0011 — $A\xrightarrow{0}B\xrightarrow{0}A\xrightarrow{1}C\xrightarrow{1}A$, ends in $A$ → accepted (two 0's, two 1's, both even). String 010 ends in $C$ → rejected.

Non-deterministic Finite Automaton (NFA)

An NFA is a 5-tuple $M = (Q, \Sigma, \delta, q_0, F)$ where the transition function maps a state and an input symbol to a set of states:

From a given state on a given symbol an NFA may move to zero, one, or several states (non-determinism). A string is accepted if some sequence of choices leads to a final state. NFAs accept exactly the regular languages, the same class as DFAs.

NFA for strings ending with 01

NFA Transition Table

$q_0$ loops on 0 and 1 (guessing the rest of the string), branches to $q_1$ on a 0, then $q_2$ on the following 1.

Subset Construction (NFA → DFA)

Start from $\{q_0\}$ and compute reachable subsets.

Accepting states: any subset containing $q_2$, i.e. $C$. $F=\{C\}$.

Resulting DFA

• States: $A, B, C$
• Start: $A$, Final: $C$

Diagram (described): $A$ on 0 → $B$, on 1 → $A$ (self-loop). $B$ on 0 → $B$ (self-loop), on 1 → $C$. $C$ (double circle) on 0 → $B$, on 1 → $A$.

Check: 001 → $A\xrightarrow{0}B\xrightarrow{0}B\xrightarrow{1}C$ → accepted.

Pumping Lemma for Regular Languages

Statement. If $L$ is a regular language, then there exists a constant $p \ge 1$ (the pumping length) such that every string $w \in L$ with $|w| \ge p$ can be written as $w = xyz$ satisfying:

1. $|y| \ge 1$ (the middle part is non-empty),
2. $|xy| \le p$,
3. $xy^{i}z \in L$ for all $i \ge 0$.

Proof (sketch)

Since $L$ is regular, there is a DFA $M$ with $p$ states accepting $L$. Take any $w \in L$ with $|w| \ge p$. While reading $w$, $M$ visits $|w|+1 > p$ states, so by the pigeonhole principle some state $q$ is repeated within the first $p$ symbols. Let:

• $x$ = prefix read before first visiting $q$,
• $y$ = part read on the loop from $q$ back to $q$ ($|y|\ge 1$, and $|xy|\le p$),
• $z$ = remainder.

The loop labelled $y$ can be traversed any number of times, so $M$ also accepts $xy^{i}z$ for every $i \ge 0$. Hence the three conditions hold. $\blacksquare$

Proving $L = \{a^{n}b^{n} \mid n \ge 0\}$ is not regular

Proof by contradiction. Assume $L$ is regular with pumping length $p$.

Choose $w = a^{p}b^{p} \in L$, with $|w| = 2p \ge p$. By the lemma $w = xyz$ with $|xy| \le p$ and $|y| \ge 1$.

Because $|xy| \le p$, the substring $xy$ lies entirely within the first $p$ symbols, which are all $a$'s. Therefore $y = a^{k}$ for some $k \ge 1$.

Pump with $i = 2$:

Since $k \ge 1$, this string has more $a$'s than $b$'s, so $a^{p+k}b^{p} \notin L$. This contradicts condition (3) of the pumping lemma.

Therefore the assumption is false, and $L = \{a^{n}b^{n} \mid n \ge 0\}$ is not regular. $\blacksquare$

• Alphabet ($\Sigma$): a finite, non-empty set of symbols. Example: $\Sigma = \{0, 1\}$ (binary alphabet); $\Sigma = \{a, b, c\}$.
• String (word): a finite sequence of symbols drawn from an alphabet. The empty string is denoted $\varepsilon$ and has length 0. Example: over $\{0,1\}$, 0110 is a string of length 4; $\varepsilon$ is the empty string.
• Language: a set of strings over an alphabet, i.e. any subset of $\Sigma^{*}$ (the set of all strings over $\Sigma$). A language may be finite or infinite. Example: $L = \{ w \in \{0,1\}^{*} \mid w \text{ has even length} \}$, or $L = \{a^{n}b^{n} \mid n \ge 0\}$.

DFA vs NFA

Important: despite the differences, DFA and NFA have equal expressive power — both accept exactly the class of regular languages, and every NFA can be converted to an equivalent DFA via subset construction (with up to $2^{n}$ states).

DFA accepting binary strings ending with 00

Track how many trailing 0's have been seen (0, 1, or $\ge 2$).

• $q_0$: last symbol was not part of a 00 suffix (start; no relevant trailing 0)
• $q_1$: string currently ends in exactly one 0
• $q_2$: string ends in 00 — accepting

Transition Table

Reading a 1 always resets to $q_0$ (suffix broken). In $q_2$, another 0 keeps the ...00 suffix, so it self-loops.

Diagram (described): $q_0\xrightarrow{0}q_1\xrightarrow{0}q_2$; $q_2$ self-loops on 0; every 1 arrow goes back to $q_0$. $q_2$ is a double circle.

Check: 1100 → $q_0\xrightarrow{1}q_0\xrightarrow{1}q_0\xrightarrow{0}q_1\xrightarrow{0}q_2$ → accepted.

$\varepsilon$-closure

For an NFA with $\varepsilon$-transitions, the $\varepsilon$-closure of a state $q$, written $\varepsilon\text{-closure}(q)$ (or $ECLOSE(q)$), is the set of all states reachable from $q$ using zero or more $\varepsilon$ (empty) transitions only (no input symbol consumed). For a set of states, the $\varepsilon$-closure is the union of the closures of its members. Every state is always in its own $\varepsilon$-closure.

It is used when simulating $\varepsilon$-NFAs and when converting an $\varepsilon$-NFA to a DFA.

Example

Consider the $\varepsilon$-transitions:

Then:

• $\varepsilon\text{-closure}(q_0) = \{q_0, q_1, q_2\}$ (reach $q_1$ directly, $q_2$ via $q_1$)
• $\varepsilon\text{-closure}(q_1) = \{q_1, q_2\}$
• $\varepsilon\text{-closure}(q_2) = \{q_2\}$
• $\varepsilon\text{-closure}(q_3) = \{q_3\}$

Regular expression: at least one 0 and at least one 1

The string must contain a 0 somewhere and a 1 somewhere (in either order). One standard answer, splitting on which symbol appears first:

• The first term covers strings where a 0 occurs before some later 1.
• The second term covers strings where a 1 occurs before some later 0.

Together they describe exactly the strings over $\{0,1\}$ containing at least one 0 and at least one 1.

(Equivalently, this is $\Sigma^{*} - (0^{*} + 1^{*})$, i.e. all strings except those made only of 0's or only of 1's, including $\varepsilon$.)

Examples accepted: 01, 10, 0011, 1010. Rejected: $\varepsilon$, 000, 111.

Arden's Theorem

Statement. Let $P$ and $Q$ be regular expressions over an alphabet, where $P$ does not contain the empty string $\varepsilon$ (i.e. $\varepsilon \notin P$). Then the equation

has the unique solution

The condition $\varepsilon \notin P$ guarantees the solution is unique.

Use: deriving a regular expression from a finite automaton

Given a DFA/NFA, Arden's theorem lets us solve the automaton's state equations:

1. For each state $q_i$, write an equation expressing it as the sum of $(\text{predecessor state}) \cdot (\text{input symbol})$ for every incoming transition. The start state's equation also includes a $\varepsilon$ term.
2. This yields a system of simultaneous regular-expression equations.
3. Solve by substitution, repeatedly applying Arden's rule $R = Q + RP \Rightarrow R = QP^{*}$ to eliminate self-loops/recursion.
4. The regular expression for the final state (sum of expressions for all final states) is the language accepted by the automaton.

Mini-example

For a state with $q_1 = \varepsilon + q_1 a$ (self-loop on $a$), Arden gives $q_1 = \varepsilon a^{*} = a^{*}$.

Ambiguous Grammar

A context-free grammar $G$ is ambiguous if there exists at least one string in $L(G)$ that has two or more distinct parse trees (equivalently, two distinct leftmost derivations, or two distinct rightmost derivations).

Example

Consider the grammar for arithmetic expressions:

Take the string id + id * id. It has two different leftmost derivations / parse trees:

Derivation 1 (treats $+$ first):

Parse tree groups as $id + (id * id)$.

Derivation 2 (treats $*$ first):

Parse tree groups as $(id + id) * id$.

Since the single string id + id * id has two distinct parse trees, the grammar is ambiguous. (It can be made unambiguous by introducing precedence levels using terms and factors.)

Eliminating Left Recursion from $A \to Aa \mid b$

General rule. For a grammar with immediate left recursion of the form

(where $\beta$ does not begin with $A$), replace it by the right-recursive grammar:

Applying to $A \to Aa \mid b$: here $\alpha = a$ and $\beta = b$. Substituting:

Verification. The original grammar generates $b a^{*}$ (a $b$ followed by zero or more $a$'s). The new grammar also generates $b$ then any number of $a$'s, e.g. baa: $A \Rightarrow bA' \Rightarrow baA' \Rightarrow baaA' \Rightarrow baa$. The languages are equal, and there is no longer any left recursion.

Greibach Normal Form (GNF)

A CFG is in Greibach Normal Form if every production has the form

where $a$ is a single terminal and $\alpha$ is a (possibly empty) string of variables only ($\alpha \in V^{*}$). Thus every production begins with exactly one terminal. (If $\varepsilon \in L$, the production $S \to \varepsilon$ is also permitted.)

Conversion Procedure

Given a CFG (with no $\varepsilon$-productions except possibly $S\to\varepsilon$, no unit productions, no useless symbols):

1. Convert to Chomsky Normal Form (CNF) first — productions $A \to BC$ or $A \to a$. Remove $\varepsilon$-, unit, and useless productions along the way.
2. Order the variables $A_1, A_2, \dots, A_n$.
3. Remove forward recursion: for each production $A_i \to A_j\gamma$ with $j < i$, substitute every production of $A_j$ for the leading $A_j$, so that the leading variable's index is not smaller. Repeat until every production starts with a higher-indexed variable or a terminal.
4. Eliminate immediate left recursion of the form $A_i \to A_i\alpha$ by introducing a new variable $B_i$ (right-recursion conversion).
5. Back-substitute: now $A_n$'s productions start with a terminal. Substitute these into $A_{n-1}, A_{n-2}, \dots$ so every production begins with a terminal.
6. Fix the new variables $B_i$ similarly so their productions also begin with terminals.
7. Replace any leading-position terminal that is followed by terminals by introducing variables, so each production becomes $A \to a\alpha$ with $\alpha$ over variables only.

The result is an equivalent grammar in GNF. GNF is useful because every derivation step produces exactly one terminal, so a string of length $n$ derives in exactly $n$ steps, and GNF directly relates CFGs to pushdown automata.