Theory of Computation (AD-501) Unit 4 Notes

How unit 4 is examined

This unit covers PDA design, PDA versus CFG conversions and Petri nets; the marks are in PDA design (three 7-mark questions), then parsing and ambiguity, NPDA to CFG, and Petri nets.

Example of PDA

<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. A PDA is a 7-tuple $M=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$: a finite automaton with a stack, where $\delta(q,a,X)$ gives moves $(p,\gamma)$ that read $a$ (or $\varepsilon$), pop $X$ and push $\gamma$.

Key points.

Acceptance is by final state (reach a state in $F$) or by empty stack (stack becomes empty after the whole input); read the question for which one.
For $a^nb^n$, push one symbol per $a$, pop one per $b$, and move to the final state only when the stack is back to $Z_0$.
For equal $a$s and $b$s, the stack holds the excess symbol: a matching symbol is pushed, the opposite symbol is popped.
For odd palindromes $wxw^R$, push the first half, guess the middle nondeterministically, then pop and match the second half.
A string is rejected when no move exists or the stack is not balanced at the end.

Diagram. $a^nb^n$ ($Z$ = $Z_0$; $q_2$ final)

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-01" viewBox="0 0 424 80" width="424" height="80" role="img" aria-label="PDA for a^n b^n, n>=1, by final state; e means epsilon. Self-loop on q0 is a,Z/aZ and a,a/aa; self-loop on q1 is b,a/e."><style>#dsfig-u4-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-01 .t{fill:#16181D;font-weight:500}#dsfig-u4-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-01 .dot{fill:#16181D}#dsfig-u4-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-01 .ah{fill:#454C5A}#dsfig-u4-01 .ah.hi{fill:#2340B8}#dsfig-u4-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-01 .e{stroke:#B1B7C3}html.dark #dsfig-u4-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-01 .t{fill:#E6E8ED}html.dark #dsfig-u4-01 .t.inv{fill:#0F1115}html.dark #dsfig-u4-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-01 .dot{fill:#E6E8ED}html.dark #dsfig-u4-01 .ann{fill:#8FA3FF}html.dark #dsfig-u4-01 .lbl{fill:#858D9C}html.dark #dsfig-u4-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-01 .ah{fill:#B1B7C3}html.dark #dsfig-u4-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah5" 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="ahh5" 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(#ah5)"/><path class="e" d="M231,40 L363,40" marker-end="url(#ah5)"/><g class="wl"><rect x="102.5" y="31" width="47.1" height="18" rx="9"/><text class="t" x="126" y="40" dy=".35em" text-anchor="middle">b,a/e</text></g><g class="wl"><rect x="274.5" y="31" width="47.1" height="18" rx="9"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">e,Z/Z</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">PDA for a^n b^n, n>=1, by final state; e means epsilon. Self-loop on q0 is a,Z/aZ and a,a/aa; self-loop on q1 is b,a/e.</figcaption></figure>

Example. (a) $a^nb^n$: $\delta(q_0,a,Z)=(q_0,aZ)$, $\delta(q_0,a,a)=(q_0,aa)$, $\delta(q_0,b,a)=(q_1,\varepsilon)$, $\delta(q_1,b,a)=(q_1,\varepsilon)$, $\delta(q_1,\varepsilon,Z)=(q_2,Z)$. Trace of aaaabbab: four $a$s give stack $aaaaZ$; two $b$s leave $aaZ$; the next symbol $a$ in $q_1$ has no move, so it is rejected.

(b) $n_a=n_b$, final state: for $x\in\{a,b\}$ and $y$ the other symbol, $\delta(q_0,x,Z)=(q_0,xZ)$, $\delta(q_0,x,x)=(q_0,xx)$, $\delta(q_0,x,y)=(q_0,\varepsilon)$, $\delta(q_0,\varepsilon,Z)=(q_1,Z)$, $q_1$ final. abba: $aZ\to Z\to bZ\to Z\to q_1$, accepted.

(c) Odd palindromes, empty stack: for $x\in\{a,b\}$ and $X\in\{Z,a,b\}$, $\delta(q_0,x,X)=\{(q_0,xX),(q_1,X)\}$ (push, or take $x$ as the middle); $\delta(q_1,x,x)=(q_1,\varepsilon)$; $\delta(q_1,\varepsilon,Z)=(q_1,\varepsilon)$. For a centre marker $c$ ($wcw^R$) use $\delta(q_0,c,X)=(q_1,X)$. ababa: push $a,b$; middle $a$; pop $b,a$; pop $Z$; stack empty, accepted.

Answer frame. Open with the language and the acceptance mode; draw the transition diagram with labels $input,top/push$; list the transitions with one line on what each does; finish with the trace of the given string and the verdict.

Asked: [7 marks] (Nov 2022) Design a PDA for $L=\{x \mid n_a(x)=n_b(x),\ x\in\{a,b\}^*\}$ by final state. Asked: [7 marks] (Nov 2022) Construct a PDA for odd palindromes over $\{a,b\}$ by empty stack. Asked: [7 marks] (Nov 2023) Design a PDA for $L=\{a^nb^n \mid n\ge1\}$; check the acceptability of "aaaabbab".

Deterministic and non-deterministic PDAs

Definition. A PDA is deterministic (DPDA) if every configuration has at most one move; otherwise it is non-deterministic (NPDA).

A DPDA has no two choices for the same state, input and stack top, and no $\varepsilon$-move clashing with an input move.
Unlike finite automata, NPDA is strictly more powerful: $ww^R$ needs an NPDA, while $wcw^R$ and $a^nb^n$ need only a DPDA.
DPDAs accept the deterministic CFLs, a proper subset of CFLs.

Context free grammar

Definition. A CFG is $G=(V,T,P,S)$ with variables $V$, terminals $T$, productions $P$ of the form $A\to\alpha$ ($A$ one variable, $\alpha\in(V\cup T)^*$) and start symbol $S$.

$L(G)=\{w\in T^*\mid S\Rightarrow^* w\}$; such a language is a context free language.
The left side is a single variable, so a variable is replaced regardless of context.
Derivations are shown as derivation (parse) trees.

Parsing

Definition. <mark>Parsing is finding a derivation (parse tree) of a string from the start symbol of a CFG, or showing there is none.</mark>

A leftmost derivation always replaces the leftmost variable; a rightmost derivation the rightmost one.
Each parse tree has exactly one leftmost and one rightmost derivation, so a string with two leftmost derivations (or two rightmost) has two parse trees and the grammar is ambiguous.
Example $E\to E+E\mid E*E\mid id$, string $id+id*id$: leftmost 1 is $E\Rightarrow E+E\Rightarrow id+E\Rightarrow id+E*E\Rightarrow id+id*E\Rightarrow id+id*id$; leftmost 2 is $E\Rightarrow E*E\Rightarrow E+E*E\Rightarrow id+E*E\Rightarrow id+id*E\Rightarrow id+id*id$. They give $id+(id*id)$ and $(id+id)*id$: two trees.
Parsers are top-down (build a leftmost derivation from $S$) or bottom-up (build a rightmost derivation in reverse).

Asked: [7 marks] (Nov 2023) What do you mean by parsing? How do leftmost and rightmost derivations help to find the ambiguity in a grammar?

Ambiguity

Definition. A CFG is ambiguous if some string in $L(G)$ has two or more distinct parse trees (equivalently two leftmost derivations).

Ambiguity is a property of the grammar, not the language; many ambiguous grammars can be rewritten unambiguously by fixing precedence and associativity.
A language for which every grammar is ambiguous is inherently ambiguous, for example $\{a^ib^jc^k\mid i=j \text{ or } j=k\}$.
No algorithm can decide whether an arbitrary CFG is ambiguous.

Normal forms of CFGs

Definition. Normal forms restrict production shapes without changing the language (ignoring $\varepsilon$).

Chomsky normal form (CNF): every production is $A\to BC$ or $A\to a$.
Greibach normal form (GNF): every production is $A\to a\alpha$ with $\alpha$ a string of variables.
First remove $\varepsilon$-productions, unit productions and useless symbols; then convert.
In CNF a string of length $n$ needs $2n-1$ derivation steps.

CFG to NPDA

Definition. For a CFG $G$ build an NPDA with one state $q$ that accepts $L(G)$ by empty stack.

Start with $S$ on the stack.
For each production $A\to\alpha$ add $\delta(q,\varepsilon,A)\ni(q,\alpha)$: a variable on top is replaced by the right side.
For each terminal $a$ add $\delta(q,a,a)=(q,\varepsilon)$: a terminal on top is matched with the input and popped.
The NPDA simulates a leftmost derivation.

NPDA to CFGs

Formula. <mark>Variables are triplets $[qXp]$ meaning "from state $q$ with $X$ on top, the stack sinks below $X$ and the state becomes $p$"; start $S_0\to[q_0Z_0p]$ for every state $p$.</mark>

For $\delta(q,a,X)\ni(r,\varepsilon)$ add $[qXr]\to a$.
For $\delta(q,a,X)\ni(r,Y_1\cdots Y_k)$ add $[qXs_k]\to a[rY_1s_1][s_1Y_2s_2]\cdots[s_{k-1}Y_ks_k]$ for all state choices $s_i$.
Write $[0S1]$ for $[q_0Sq_1]$. Here start $S_0\to[0S0]\mid[0S1]$ and:

Move	Productions
$\delta(q_0,\varepsilon,S)=(q_0,\varepsilon)$	$[0S0]\to\varepsilon$
$\delta(q_0,1,S)=(q_0,AS)$	$[0Sr]\to1[0Ap][pSr]$, $p,r\in\{0,1\}$
$\delta(q_0,1,A)=(q_0,AA)$	$[0Ar]\to1[0Ap][pAr]$
$\delta(q_0,1,A)=(q_1,\varepsilon)$	$[0A1]\to1$
$\delta(q_0,0,A)=(q_1,A)$	$[0Ar]\to0[1Ar]$
$\delta(q_1,0,S)=(q_0,S)$	$[1Sr]\to0[0Sr]$

There are no moves from $q_1$ on $A$, so $[1A0],[1A1]$ are useless and the reduced grammar is $S_0\to[0S0]$; $[0S0]\to\varepsilon\mid1[0A1][1S0]$; $[0A1]\to1$; $[1S0]\to0[0S0]$. It generates $(110)^*$.

Asked: [7 marks] (Nov 2022) Construct the CFG for the PDA $A=(\{q_0,q_1\},\{0,1\},\{S,A\},\delta,q_0,S,\varphi)$ with $\delta(q_0,1,S)=\{(q_0,AS)\}$, $\delta(q_0,\varepsilon,S)=\{(q_0,\varepsilon)\}$, $\delta(q_0,1,A)=\{(q_0,AA)\}$, $\delta(q_0,0,A)=\{(q_1,A)\}$, $\delta(q_0,1,A)=\{(q_1,\varepsilon)\}$, $\delta(q_1,0,S)=\{(q_0,S)\}$.

CFG equivalent to PDA

Definition. A language is context free if and only if some PDA accepts it.

CFG to PDA: the one-state NPDA that simulates leftmost derivations by empty stack.
PDA to CFG: the triplet grammar $[qXp]$.
Acceptance by empty stack and by final state are equivalent in power.
Hence CFLs are exactly the languages of NPDAs.

Petri nets model

Definition. <mark>A Petri net is a bipartite directed graph of places (circles), transitions (bars) and weighted arcs, with tokens in places; formally $(P,T,I,O,M_0)$ with initial marking $M_0$.</mark>

A marking $M$ gives the number of tokens in each place.
A transition is enabled when every input place holds at least as many tokens as the arc weight.
Firing removes tokens from the input places and adds tokens to the output places, giving a new marking.
Petri nets model concurrency, synchronisation and resource sharing, for example in protocols and workflows.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-02" viewBox="0 0 424 252" width="424" height="252" role="img" aria-label="Net for 2H2 + O2 -> 2H2O; H2 has 2 tokens, O2 has 1, H2O 0. Firing T gives H2O 2 tokens."><style>#dsfig-u4-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-02 .t{fill:#16181D;font-weight:500}#dsfig-u4-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-02 .dot{fill:#16181D}#dsfig-u4-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-02 .ah{fill:#454C5A}#dsfig-u4-02 .ah.hi{fill:#2340B8}#dsfig-u4-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-02 .e{stroke:#B1B7C3}html.dark #dsfig-u4-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-02 .t{fill:#E6E8ED}html.dark #dsfig-u4-02 .t.inv{fill:#0F1115}html.dark #dsfig-u4-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-02 .dot{fill:#E6E8ED}html.dark #dsfig-u4-02 .ann{fill:#8FA3FF}html.dark #dsfig-u4-02 .lbl{fill:#858D9C}html.dark #dsfig-u4-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-02 .ah{fill:#B1B7C3}html.dark #dsfig-u4-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah6" 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="ahh6" 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,48.5 L193.2,116.6" marker-end="url(#ah6)"/><path class="e" d="M57,203.5 L193.2,135.4" marker-end="url(#ah6)"/><path class="e" d="M231,126 L363,126" marker-end="url(#ah6)"/><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">2</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">1</text></g><g class="wl"><rect x="288.4" y="117" width="19.2" height="18" rx="9"/><text class="t" x="298" y="126" dy=".35em" text-anchor="middle">2</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">H2</text><circle class="n" cx="40" cy="212" r="18"/><text class="t" x="40" y="212" dy=".35em" text-anchor="middle">O2</text><circle class="n" cx="212" cy="126" r="18"/><text class="t" x="212" y="126" dy=".35em" text-anchor="middle">T</text><circle class="n" cx="384" cy="126" r="18"/><text class="t" x="384" y="126" dy=".35em" text-anchor="middle">H2O</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Net for 2H2 + O2 -> 2H2O; H2 has 2 tokens, O2 has 1, H2O 0. Firing T gives H2O 2 tokens.</figcaption></figure>

Answer frame. Open with the definition; draw the net with tokens; explain enabling and firing on it; close with the marking before and after and an application.

Asked: [7 marks] (Nov 2023) Explain the Petri nets model with example.

Last-minute revision

PDA = finite automaton + stack; 7-tuple $(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)$.
$a^nb^n$: push on $a$, pop on $b$, go to final on $Z_0$.
Equal $a$/$b$ counts: push same symbol, pop opposite symbol.
Odd palindromes need a guessed middle, so an NPDA.
NPDA is stronger than DPDA; DPDA gives deterministic CFLs only.
Ambiguous means two parse trees, or two leftmost derivations, for one string.
CNF: $A\to BC\mid a$; GNF: $A\to a\alpha$.
CFG to PDA: $\delta(q,\varepsilon,A)\ni(q,\alpha)$ and $\delta(q,a,a)=(q,\varepsilon)$.
PDA to CFG: variables $[qXp]$, pop gives $[qXr]\to a$.
Petri net: places, transitions, tokens; enabled means enough tokens; firing moves tokens.

Memory hooks

Push the first, pop the match: PDA counting.
Palindrome: guess the middle, then mirror.
Two trees, two leftmost derivations: ambiguous.
Triplet $[qXp]$: from q, pop X, land in p.
Petri: Places hold, Transitions fire.

Coverage checklist

example of PDA: Nov 2022 (two), Nov 2023
deterministic and non-deterministic PDAs: covered, not asked
Context Free Grammar: covered, not asked
Parsing: Nov 2023
Ambiguity: covered, not asked
Normal form of CFGs: covered, not asked
CFG to NPDA: covered, not asked
NPDA to CFGs: Nov 2022
CFG equivalent to PDA: covered, not asked
Petri nets model: Nov 2023

Account

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