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

Non-deterministic Finite Automaton (NFA)

An NFA is a finite automaton defined by the 5-tuple $M = (Q, \Sigma, \delta, q_0, F)$ where:

• $Q$ = finite set of states
• $\Sigma$ = input alphabet
• $\delta : Q \times (\Sigma \cup \{\epsilon\}) \rightarrow 2^Q$ is the transition function (it maps to a set of states)
• $q_0 \in Q$ = start state
• $F \subseteq Q$ = set of final (accepting) states

Unlike a DFA, from a given state on a given symbol an NFA may move to zero, one, or several states. A string is accepted if at least one computation path ends in a final state.

NFA for strings over {0,1} ending with '01'

States: $q_0$ (start), $q_1$ (seen 0), $q_2$ (seen 01, final).

The self-loop on $q_0$ (for both 0 and 1) lets the automaton guess where the suffix 01 begins; $q_0 \xrightarrow{0} q_1 \xrightarrow{1} q_2$ recognises the final 01. $q_2$ is the only accepting state.

Conversion to DFA (Subset Construction)

We build DFA states as subsets of NFA states. Start = $\{q_0\}$.

Resulting DFA:

• States: $A, B, C$
• Start state: $A$
• Accepting state: $C$ (since $C$ contains the NFA final state $q_2$)
• Transitions as in the table above.

This DFA accepts exactly the strings over $\{0,1\}$ ending in 01.

Pumping Lemma for Regular Languages

Statement. If $L$ is a regular language, then there exists a constant $p$ (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^iz \in L$ for every $i \ge 0$.

Proof

Since $L$ is regular, some DFA $M$ with $p$ states accepts $L$. Take any $w \in L$ with $|w| \ge p$. Reading $w$ visits $|w|+1 \ge p+1$ states. By the pigeonhole principle, among the first $p+1$ visited states some state $q$ repeats while reading the first $p$ symbols.

Let the first visit to $q$ be after reading $x$ and the second after reading $xy$ (so the loop reads $y$, $|y|\ge 1$, and $|xy| \le p$). The remaining input is $z$. Because $y$ takes $M$ from $q$ back to $q$, the loop can be traversed any number of times. Hence $xy^iz$ is also accepted for all $i \ge 0$, i.e. $xy^iz \in L$. $\blacksquare$

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

Assume, for contradiction, that $L$ is regular with pumping length $p$.

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

Since $|xy| \le p$, both $x$ and $y$ lie entirely within the leading $a$'s, so $y = a^k$ for some $k \ge 1$.

Now pump with $i = 2$:

$$xy^2z = a^{p+k} b^p.$$

Here the number of $a$'s ($p+k$) exceeds the number of $b$'s ($p$), so $xy^2z \notin L$.

This contradicts the pumping lemma. Therefore $L = \{a^n b^n \mid n \ge 0\}$ is not regular. $\blacksquare$

Context-Free Grammar (CFG)

A CFG is a 4-tuple $G = (V, T, P, S)$ where $V$ is a finite set of variables (non-terminals), $T$ is a finite set of terminals ($V \cap T = \emptyset$), $S \in V$ is the start symbol, and $P$ is a finite set of productions of the form $A \to \alpha$ with $A \in V$ and $\alpha \in (V \cup T)^*$. The language generated is the set of terminal strings derivable from $S$.

Chomsky Normal Form (CNF): every production is $A \to BC$ (two variables) or $A \to a$ (single terminal); $S \to \epsilon$ is allowed only if $\epsilon \in L$.

Converting the given CFG to CNF

Grammar:

$$S \to ASA \mid aB, \quad A \to B \mid S, \quad B \to b \mid \epsilon$$

Step 1: Add a new start symbol

$$S_0 \to S, \quad S \to ASA \mid aB, \quad A \to B \mid S, \quad B \to b \mid \epsilon$$

Step 2: Remove $\epsilon$-productions

Nullable variable: $B$ (since $B \to \epsilon$), and hence $A$ (since $A \to B$). Remove $B \to \epsilon$ and add versions of rules with nullable symbols omitted.

• $S \to ASA$: dropping nullable $A$'s gives $S \to SA \mid AS \mid S$. Drop the unit $S\to S$. So $S \to ASA \mid SA \mid AS$.
• $S \to aB$: gives $S \to aB \mid a$.
• $A \to B$ stays; $A \to \epsilon$ would appear (A nullable) but we drop it.

Result:

$$S_0 \to S$$ $$S \to ASA \mid SA \mid AS \mid aB \mid a$$ $$A \to B \mid S$$ $$B \to b$$

Step 3: Remove unit productions

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

• $S_0 \to ASA \mid SA \mid AS \mid aB \mid a$
• $A \to b$ (from $A\to B\to b$), and $A \to ASA \mid SA \mid AS \mid aB \mid a$ (from $A\to S$).

Result:

$$S_0 \to ASA \mid SA \mid AS \mid aB \mid a$$ $$S \to ASA \mid SA \mid AS \mid aB \mid a$$ $$A \to ASA \mid SA \mid AS \mid aB \mid a \mid b$$ $$B \to b$$

Step 4: Replace terminals in long rules

Introduce $X_a \to a$. Replace a in $aB$ by $X_a$: $\,\to X_aB$.

Step 5: Break rules longer than two symbols

For each $ASA$ introduce $Y \to SA$, so $ASA \to A Y$ with $Y \to SA$.

Final CNF Grammar

$$S_0 \to AY \mid SA \mid AS \mid X_aB \mid a$$ $$S \to AY \mid SA \mid AS \mid X_aB \mid a$$ $$A \to AY \mid SA \mid AS \mid X_aB \mid a \mid b$$ $$B \to b$$ $$X_a \to a$$ $$Y \to SA$$

Every production now has the form $A \to BC$ or $A \to a$, so the grammar is in Chomsky Normal Form.

Closure Properties of Regular Languages

The class of regular languages is closed under the following operations: if $L_1$ and $L_2$ are regular, then so are the results below.

• Union: $L_1 \cup L_2$ is regular (combine the two FAs with a new start state via $\epsilon$-moves, or take the union of their regular expressions $r_1 + r_2$).
• Concatenation: $L_1 L_2$ is regular (connect final states of $M_1$ to start of $M_2$ by $\epsilon$; regex $r_1 r_2$).
• Kleene Star: $L_1^*$ is regular (add $\epsilon$-loop back from finals to start).
• Intersection: $L_1 \cap L_2$ is regular (product/cross-product DFA construction).
• Complement: $\overline{L_1}$ is regular (swap accepting and non-accepting states of a complete DFA).
• Difference: $L_1 - L_2 = L_1 \cap \overline{L_2}$ is regular.
• Reversal: $L_1^R$ is regular (reverse all transitions, swap start/final).
• Homomorphism and inverse homomorphism also preserve regularity.

These closure properties are useful for proving languages regular/non-regular and for combining automata in lexical analysis.

Membership Problem

The membership problem asks: given a grammar (or automaton) $G$ and a string $w$, decide whether $w \in L(G)$. For context-free languages this is decidable — the CYK algorithm answers it efficiently.

CYK Algorithm (Cocke–Younger–Kasami)

CYK is a dynamic-programming, bottom-up parsing algorithm that decides membership for a CFG in Chomsky Normal Form. For a string $w = a_1a_2\dots a_n$:

1. Build a triangular table $V[i,j]$ where $V[i,j]$ holds the set of variables that derive the substring of length $j$ starting at position $i$.
2. Base case (length 1): $V[i,1] = \{A \mid A \to a_i \in P\}$.
3. Recursive case: for length $j$ from 2 to $n$, for each split point $k$, set

$$A \in V[i,j] \text{ if } A \to BC, \; B \in V[i,k], \; C \in V[i+k, j-k].$$

4. Accept if the start symbol $S \in V[1,n]$.

It runs in $O(n^3 \cdot |G|)$ time, confirming CFG membership is decidable.

NFA for $(0+1)^*1$

This regular expression denotes all strings over $\{0,1\}$ that end with 1.

States: $q_0$ (start), $q_1$ (final).

Description: $q_0$ has self-loops on both 0 and 1, modelling the $(0+1)^*$ part. On reading a 1, the NFA may also move to the accepting state $q_1$, modelling the final 1. A string is accepted iff some path lands in $q_1$ after the last symbol — which happens exactly when the last input symbol is 1.

• $Q = \{q_0, q_1\}$, start $= q_0$, $F = \{q_1\}$, $\Sigma=\{0,1\}$.

Rice's Theorem

Statement. Every non-trivial semantic property of the language recognised by a Turing machine is undecidable.

More precisely, let $P$ be a property of recursively enumerable languages (i.e. a property of the language $L(M)$, not of the machine's internal structure). $P$ is non-trivial if some TM-recognisable language has the property and some other does not. Then the problem "Does $L(M)$ have property $P$?" is undecidable.

Key points:

• The property must be about the language (behaviour), not about syntax/states (e.g. "M has 5 states" is not covered).
• Non-trivial means $P$ is neither always true nor always false over all RE languages.

Examples of undecidable problems (by Rice): Is $L(M) = \emptyset$? Is $L(M)$ regular? Is $L(M)$ finite? Does $M$ accept a particular string $w$? All are undecidable.

Rice's theorem is a powerful generalisation of the halting problem, showing that essentially nothing interesting about a TM's language can be decided algorithmically.

Alphabet, String, and Language

Alphabet ($\Sigma$): a finite, non-empty set of symbols. Example: $\Sigma = \{0, 1\}$ (binary alphabet), or $\Sigma = \{a, b, c\}$.

String (word): a finite sequence of symbols drawn from an alphabet. The empty string is denoted $\epsilon$ (length 0). The length of string $w$ is written $|w|$. Example: over $\Sigma=\{0,1\}$, 0110 is a string with $|0110| = 4$; $\epsilon$ is also a string.

Language: a set of strings over an alphabet, i.e. any subset of $\Sigma^*$ (where $\Sigma^*$ is the set of all strings over $\Sigma$). A language may be finite or infinite. Example: over $\Sigma=\{0,1\}$:

• $L_1 = \{0, 01, 011\}$ — a finite language.
• $L_2 = \{w \mid w \text{ ends with } 1\}$ — an infinite language.
• $L_3 = \{a^nb^n \mid n \ge 0\}$ over $\{a,b\}$.

Thus: symbols form an alphabet, sequences of symbols form strings, and sets of strings form languages.

Difference between DFA and NFA

Key point: Although NFAs appear more powerful, every NFA can be converted to an equivalent DFA, so both accept exactly the same class of languages (regular languages).

DFA Accepting Binary Strings Ending with '00'

We track how many trailing 0s have been seen.

States: $q_0$ (no useful suffix / last symbol not contributing), $q_1$ (string ends in a single 0), $q_2$ (string ends in 00, accepting).

• $Q = \{q_0, q_1, q_2\}$, start $= q_0$, $F = \{q_2\}$, $\Sigma = \{0,1\}$.

Logic:

• Reading 1 always resets to $q_0$ (no trailing zeros).
• Reading 0 from $q_0$ goes to $q_1$ (one trailing zero); from $q_1$ to $q_2$ (two or more); from $q_2$ stays in $q_2$ (still ends in 00).

The DFA accepts iff it ends in $q_2$, i.e. the string ends with 00. Example: 100 is accepted; 010 is rejected.

Epsilon-Closure

In an NFA with $\epsilon$-transitions, the $\epsilon$-closure of a state $q$, written $ECLOSE(q)$ or $\epsilon\text{-}closure(q)$, is the set of all states reachable from $q$ using zero or more $\epsilon$-transitions (including $q$ itself).

Formally:

• $q \in \epsilon\text{-}closure(q)$.
• If $p \in \epsilon\text{-}closure(q)$ and there is an $\epsilon$-transition $p \to r$, then $r \in \epsilon\text{-}closure(q)$.

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

Example

Consider an $\epsilon$-NFA with transitions:

$$q_0 \xrightarrow{\epsilon} q_1, \quad q_1 \xrightarrow{\epsilon} q_2, \quad q_1 \xrightarrow{a} q_3.$$

Then:

• $\epsilon\text{-}closure(q_0) = \{q_0, q_1, q_2\}$ (reach $q_1$ via one $\epsilon$, then $q_2$ via another).
• $\epsilon\text{-}closure(q_1) = \{q_1, q_2\}$.
• $\epsilon\text{-}closure(q_3) = \{q_3\}$ (no outgoing $\epsilon$-moves).

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

For strings over $\{0,1\}$ containing at least one 0 AND at least one 1, account for the two possible orderings (the first 0 may come before or after the first 1):

$$(0+1)^*\,0\,(0+1)^*\,1\,(0+1)^* \;+\; (0+1)^*\,1\,(0+1)^*\,0\,(0+1)^*$$

Explanation:

• The first term $(0+1)^* 0 (0+1)^* 1 (0+1)^*$ matches strings where a 0 appears somewhere before a 1.
• The second term covers the case where a 1 appears before a 0.
• Their union guarantees the string has both at least one 0 and at least one 1, in either order.

Examples accepted: 01, 10, 0011, 1010. Rejected: 000, 111, \epsilon (each lacks one of the symbols).