Theory of Computation (AD-501) - Unit 2 Short Notes

How unit 2 is examined

This unit covers NFA, DFA, conversions, minimization, regular expressions, Arden's theorem and closure properties; closure properties (14 marks), DFA design and Arden's theorem carry the marks.

Non Deterministic Finite Automata (NDFA)

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>An NFA is a 5-tuple $(Q,\Sigma,\delta,q_0,F)$ where $\delta: Q\times\Sigma \to 2^Q$ maps a state and symbol to a set of next states, and a string is accepted if at least one path ends in a final state.</mark>

Key points.

1. From one state a symbol may lead to zero, one or many states, so the machine can guess.
2. Missing transitions are allowed; a path that gets stuck simply dies, so no dead state is needed.
3. Every NFA has an equivalent DFA, so NFAs accept exactly the regular languages.
4. Design tip for "no aa and no bb": remember only the last symbol read; the string must alternate.

Example. No aa, no bb: $q_0$ start, $q_a$ = last symbol a, $q_b$ = last symbol b; all states final.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-01" viewBox="0 0 252 252" width="252" height="252" role="img" aria-label="NFA for strings with neither aa nor bb; S0 start, Qa and Qb (last symbol a or b) and S0 are all final. There is no move on a from Qa or on b from Qb, so aa or bb dies."><style>#dsfig-u2-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-01 .t{fill:#16181D;font-weight:500}#dsfig-u2-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-01 .dot{fill:#16181D}#dsfig-u2-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-01 .ah{fill:#454C5A}#dsfig-u2-01 .ah.hi{fill:#2340B8}#dsfig-u2-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-01 .e{stroke:#B1B7C3}html.dark #dsfig-u2-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-01 .t{fill:#E6E8ED}html.dark #dsfig-u2-01 .t.inv{fill:#0F1115}html.dark #dsfig-u2-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-01 .dot{fill:#E6E8ED}html.dark #dsfig-u2-01 .ann{fill:#8FA3FF}html.dark #dsfig-u2-01 .lbl{fill:#858D9C}html.dark #dsfig-u2-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-01 .ah{fill:#B1B7C3}html.dark #dsfig-u2-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh2" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M57,117.5 L193.2,49.4" marker-end="url(#ah2)"/><path class="e" d="M57,134.5 L193.2,202.6" marker-end="url(#ah2)"/><path class="e" d="M205.4,57.8 Q180,126 204.7,192.3" marker-end="url(#ah2)"/><path class="e" d="M218.6,194.2 Q244,126 219.3,59.7" marker-end="url(#ah2)"/><g class="wl"><rect x="116.4" y="74" width="19.2" height="18" rx="9"/><text class="t" x="126" y="83" dy=".35em" text-anchor="middle">a</text></g><g class="wl"><rect x="116.4" y="160" width="19.2" height="18" rx="9"/><text class="t" x="126" y="169" dy=".35em" text-anchor="middle">b</text></g><g class="wl"><rect x="182.9" y="116.5" width="19.2" height="18" rx="9"/><text class="t" x="192.5" y="125.5" dy=".35em" text-anchor="middle">b</text></g><g class="wl"><rect x="221.9" y="117.5" width="19.2" height="18" rx="9"/><text class="t" x="231.5" y="126.5" dy=".35em" text-anchor="middle">a</text></g><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">S0</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">Qa</text><circle class="n" cx="212" cy="212" r="18"/><text class="t" x="212" y="212" dy=".35em" text-anchor="middle">Qb</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">NFA for strings with neither aa nor bb; S0 start, Qa and Qb (last symbol a or b) and S0 are all final. There is no move on a from Qa or on b from Qb, so aa or bb dies.</figcaption></figure>

Asked: [7 marks] (Nov 2022) Design an NFA accepting strings containing neither aa nor bb.

Deterministic finite automata machines

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>A DFA is a 5-tuple $(Q,\Sigma,\delta,q_0,F)$ with $\delta: Q\times\Sigma\to Q$, so every state has exactly one move on every symbol and each string follows one path.</mark>

Key points.

1. $Q$ is a finite set of states, $\Sigma$ the alphabet, $q_0$ the start state and $F\subseteq Q$ the final states.
2. Design method: decide what each state must remember (a count, the last symbol), one state per situation.
3. Counting a symbol up to a limit needs limit+1 states, the last one meaning "more than the limit".
4. A trap (dead) state loops to itself on every symbol and is added when a string can no longer be accepted.
5. A string is accepted if it ends in a final state after reading the whole input.

Example 1: exactly one $a$ over $\{a,b\}$. States count a: 0, 1, more than 1.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-02" viewBox="0 0 424 80" width="424" height="80" role="img" aria-label="DFA for exactly one a; loops b on Q0 and Q1, loops a,b on trap Q2; Q1 is final."><style>#dsfig-u2-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-02 .t{fill:#16181D;font-weight:500}#dsfig-u2-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-02 .dot{fill:#16181D}#dsfig-u2-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-02 .ah{fill:#454C5A}#dsfig-u2-02 .ah.hi{fill:#2340B8}#dsfig-u2-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-02 .e{stroke:#B1B7C3}html.dark #dsfig-u2-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-02 .t{fill:#E6E8ED}html.dark #dsfig-u2-02 .t.inv{fill:#0F1115}html.dark #dsfig-u2-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-02 .dot{fill:#E6E8ED}html.dark #dsfig-u2-02 .ann{fill:#8FA3FF}html.dark #dsfig-u2-02 .lbl{fill:#858D9C}html.dark #dsfig-u2-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-02 .ah{fill:#B1B7C3}html.dark #dsfig-u2-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh3" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L191,40" marker-end="url(#ah3)"/><path class="e" d="M231,40 L363,40" marker-end="url(#ah3)"/><g class="wl"><rect x="116.4" y="31" width="19.2" height="18" rx="9"/><text class="t" x="126" y="40" dy=".35em" text-anchor="middle">a</text></g><g class="wl"><rect x="288.4" y="31" width="19.2" height="18" rx="9"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">a</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">Q0</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">Q1</text><circle class="n" cx="384" cy="40" r="18"/><text class="t" x="384" y="40" dy=".35em" text-anchor="middle">Q2</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">DFA for exactly one a; loops b on Q0 and Q1, loops a,b on trap Q2; Q1 is final.</figcaption></figure>

Example 2: exactly 2 a's and 2 b's. Track (a count, b count) with each count in 0, 1, 2, >2: $4\times4=16$ states $(i,j)$. On a, $i\to\min(i+1,3)$; on b, $j\to\min(j+1,3)$ (3 means more than 2). The only final state is $(2,2)$; every state with $i=3$ or $j=3$ is dead, so these can be merged into one trap state.

Answer frame. Open with the language in words and the meaning of each state; draw the transition diagram with start arrow, double-circled final state and trap state; then give the transition table; close with "final state is ... and every other string reaches the trap".

Pitfall: Forgetting the trap state or missing a transition on some symbol makes the machine an NFA, not a DFA.

Asked: [7 marks] (Nov 2022) Design a DFA accepting set of all strings containing exactly 2a's and exactly 2b's. Asked: [7 marks] (Nov 2023) Obtain DFAs to accept strings of $a$'s and $b$'s having exactly one $a$.

Conversion of NDFA to DFA

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>Subset construction: each DFA state is a set of NFA states, and the DFA start state is the $\varepsilon$-closure of $q_0$; a DFA state is final if it contains an NFA final state.</mark>

Key points.

1. $\varepsilon$-closure$(q)$ is the set of states reachable from $q$ using only $\varepsilon$ moves, including $q$ itself.
2. To remove $\varepsilon$: $\delta'(q,a)=\varepsilon\text{-closure}(\delta(\varepsilon\text{-closure}(q),a))$.
3. New final states are those whose closure contains an old final state.
4. Only reachable subsets are built; an NFA of $n$ states gives at most $2^n$ DFA states.

Example. Paper $\varepsilon$-NFA (final $q_2$; $q_0\xrightarrow{\varepsilon}q_2$).

Start is $q_0$; final states are $q_0$ and $q_2$, since their closures contain $q_2$.

Asked: [7 marks] (Nov 2023) Convert epsilon-NFA to NFA. Consider the example having states q0, q1, q2, q3 and q4.

Minimization of automata machines

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>Minimization merges equivalent states of a DFA; two states are equivalent if for every string they both accept or both reject.</mark>

Key points.

1. First remove unreachable states.
2. Partition 0: final states and non-final states.
3. Refine: split states whose transitions on some symbol go to different blocks; repeat until no block splits.
4. Each final block is one state of the minimal DFA.

Example. Table read from the paper's figure ($q_4$ final):

$P_0=\{q_0,q_1,q_2,q_3\},\{q_4\}$; on b, $q_3\to q_4$ splits it: $P_1=\{q_0,q_1,q_2\},\{q_3\},\{q_4\}$; $q_1\to q_3$ on b splits again: $P_2=\{q_0,q_2\},\{q_1\},\{q_3\},\{q_4\}$; no more splits. Minimal DFA has 4 states ($q_0\equiv q_2$).

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u2-03" viewBox="0 0 596 80" width="596" height="80" role="img" aria-label="Minimal DFA; A = {q0,q2} start, B = q1, C = q3, D = q4 final. Other moves: A b loops, B a loops, C a to B, D a to B and D b to A."><style>#dsfig-u2-03 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u2-03 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u2-03 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u2-03 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u2-03 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u2-03 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u2-03 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u2-03 .t{fill:#16181D;font-weight:500}#dsfig-u2-03 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u2-03 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u2-03 .dot{fill:#16181D}#dsfig-u2-03 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u2-03 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u2-03 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u2-03 .ah{fill:#454C5A}#dsfig-u2-03 .ah.hi{fill:#2340B8}#dsfig-u2-03 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u2-03 .wl .t{font-size:12px;font-weight:700}#dsfig-u2-03 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u2-03 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u2-03 .e{stroke:#B1B7C3}html.dark #dsfig-u2-03 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u2-03 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u2-03 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u2-03 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u2-03 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u2-03 .t{fill:#E6E8ED}html.dark #dsfig-u2-03 .t.inv{fill:#0F1115}html.dark #dsfig-u2-03 .kd{stroke:#E6E8ED}html.dark #dsfig-u2-03 .dot{fill:#E6E8ED}html.dark #dsfig-u2-03 .ann{fill:#8FA3FF}html.dark #dsfig-u2-03 .lbl{fill:#858D9C}html.dark #dsfig-u2-03 .ptr{fill:#8FA3FF}html.dark #dsfig-u2-03 .ah{fill:#B1B7C3}html.dark #dsfig-u2-03 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u2-03 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u2-03 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u2-03 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah4" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh4" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L191,40" marker-end="url(#ah4)"/><path class="e" d="M231,40 L363,40" marker-end="url(#ah4)"/><path class="e" d="M403,40 L535,40" marker-end="url(#ah4)"/><g class="wl"><rect x="116.4" y="31" width="19.2" height="18" rx="9"/><text class="t" x="126" y="40" dy=".35em" text-anchor="middle">a</text></g><g class="wl"><rect x="288.4" y="31" width="19.2" height="18" rx="9"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">b</text></g><g class="wl"><rect x="460.4" y="31" width="19.2" height="18" rx="9"/><text class="t" x="470" y="40" dy=".35em" text-anchor="middle">b</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="384" cy="40" r="18"/><text class="t" x="384" y="40" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="556" cy="40" r="18"/><text class="t" x="556" y="40" dy=".35em" text-anchor="middle">D</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Minimal DFA; A = {q0,q2} start, B = q1, C = q3, D = q4 final. Other moves: A b loops, B a loops, C a to B, D a to B and D b to A.</figcaption></figure>

Asked: [7 marks] (Nov 2023) Apply minimization of the following DFA using Equivalence theorem.

Regular expression

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>A regular expression describes a regular language using symbols of the alphabet with union $+$, concatenation and closure $*$.</mark>

Key points.

1. Primitives are $\emptyset$, $\varepsilon$ and each $a\in\Sigma$; if $r,s$ are regular expressions so are $r+s$, $rs$, $r^*$ and $(r)$.
2. Precedence is closure, then concatenation, then union.
3. Example: $(a+b)^*abb$ is all strings over $\{a,b\}$ ending in abb.
4. Regular expressions, DFAs and NFAs describe exactly the same class of languages.

Applications of regular expressions

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>Regular expressions are used wherever a text pattern must be matched by a simple machine.</mark>

Key points.

1. Lexical analysers of compilers define tokens (identifiers, numbers) as regular expressions.
2. Text editors and tools such as grep use them for search and replace.
3. Input validation of emails, phone numbers and dates uses patterns.
4. They are also used to design circuits and protocols and to convert to finite automata.

Arden's theorem

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. ==If $P$ and $Q$ are regular expressions and $P$ does not contain $\varepsilon$, then $R = Q + RP$ has the unique solution $R = QP^*$.==

Derivation. Substitute $R$ repeatedly: $R=Q+RP=Q+(Q+RP)P=Q+QP+RP^2=\dots=Q(\varepsilon+P+P^2+\dots+P^n)+RP^{n+1}$. Since $RP^{n+1}$ can produce a string only if it is long enough, the sum gives $R=QP^*$.

Steps.

1. Write one equation per state: $q_i$ = (start gets $\varepsilon$) + sum of (source state)(symbol) over incoming edges.
2. Solve a state with a self loop by Arden's theorem, then substitute into the others.
3. The answer is the union of expressions of all final states.

Example (paper figure). $q_1$ start (loop 0), $q$ final (loop 0), $q_3$ trap; $q_1\xrightarrow{1}q\xrightarrow{1}q_3$.

• $q_1=\varepsilon+q_1 0\Rightarrow q_1=0^*$
• $q=q_1 1+q\,0\Rightarrow q=0^*1\,0^*$ (Arden's theorem with $Q=0^*1$, $P=0$)

Result: $0^*10^*$.

Answer frame. Open by stating the theorem and its condition (no $\varepsilon$ in $P$); write the state equations; solve final state, substituting step by step; close with the final expression. For "applications" add: converting an FA to a regular expression, and proving equivalence of two automata.

Pitfall: Applying the theorem when $P$ contains $\varepsilon$ gives a wrong, non-unique answer.

Asked: [7 marks] (Nov 2022, Nov 2023) Convert the following Finite Automata to its equivalent Regular Expression. Construct a regular expression corresponding to the automata using Arden's theorem. Write the applications of Arden's Theorem.

Meaning of union, intersection, concatenation and closure

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>Regular languages are closed under an operation if applying it to regular languages always gives a regular language.</mark>

Key points.

1. Union $L_1\cup L_2$: regular; the regular expression is $r_1+r_2$.
2. Concatenation $L_1L_2$: strings of $L_1$ followed by strings of $L_2$; regular expression $r_1r_2$.
3. Closure (Kleene star) $L^*$: zero or more strings of $L$ joined; regular expression $r^*$.
4. Complement $\bar L=\Sigma^*-L$: regular; swap final and non-final states of a complete DFA.
5. Intersection $L_1\cap L_2$: regular by De Morgan, $L_1\cap L_2=\overline{\bar L_1\cup\bar L_2}$, or by the product DFA.
6. Also closed under difference, reversal, homomorphism and inverse homomorphism.

Example. $L_1=\{a\}$, $L_2=\{b\}$: union $\{a,b\}$, concatenation $\{ab\}$, closure of $L_1$ is $a^*$.

Other two options. Chomsky hierarchy: Type 0 unrestricted (Turing machine), Type 1 context sensitive (LBA), Type 2 context free (PDA), Type 3 regular (finite automaton), each contained in the one before. Petri net: bipartite graph of places, transitions and tokens for concurrency (Unit 4). P is solvable in polynomial time, NP verifiable in polynomial time; open question P vs NP (Unit 5).

Answer frame. Open with the definition; give each operation with its regular expression or construction in a table; end with one example and the significance that regular languages can be built and tested by combining machines.

Asked: [14 marks] (Nov 2022) Write short notes on any two of the following: a) Closure properties of Regular Language b) Chomsky hierarchy of grammar c) Petri Nets model d) P and NP Problems

2 way DFA

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>A two-way DFA has a read head that can move left or right on the input tape, with $\delta:Q\times\Sigma\to Q\times\{L,R\}$.</mark>

Key points.

1. The input is between end markers and the string is accepted if the machine moves off the right end in a final state.
2. Although it can re-read input, it accepts exactly the regular languages.
3. It may need fewer states than a one-way DFA for some languages.

Last-minute revision

• DFA: $\delta:Q\times\Sigma\to Q$; NFA: $\delta:Q\times\Sigma\to 2^Q$.
• Subset construction gives at most $2^n$ states; start state is $\varepsilon$-closure of $q_0$.
• Exactly one $a$: 3 states (0, 1, >1); exactly 2 a's and 2 b's: 16 states.
• No aa and no bb: NFA of 3 states, all final.
• Minimization: split final and non-final, then refine until stable.
• Minimal DFA of the paper table: 4 states, $q_0\equiv q_2$.
• Arden: $R=Q+RP\Rightarrow R=QP^*$, with $\varepsilon\notin P$.
• Paper Arden answer: $0^*10^*$.
• Regular languages are closed under union, intersection, concatenation, closure, complement.
• Chomsky hierarchy: Type 3 regular inside Type 2, 1, 0.

Memory hooks

• Subset construction: "power set, closure first".
• Minimization: "final vs non-final, then split by destination".
• Arden: "R equals Q P-star".
• Closure: "Complement swaps finals; intersection by De Morgan".

Coverage checklist

• Non Deterministic Finite Automata (NDFA): NFA with neither aa nor bb.
• Deterministic finite automata machines: exactly 2 a's and 2 b's; exactly one a.
• conversion of NDFA to DFA: epsilon-NFA to NFA.
• minimization of automata machines: equivalence-theorem minimization.
• regular expression: definition and rules.
• applications of regular expressions: lexers, search, validation.
• Arden’s theorem: FA to regular expression; applications.
• Meaning of union, intersection, concatenation and closure: short notes, closure properties.
• 2 way DFA: definition and power.