Notes - Models of Computation MT23, Context-free grammars

A 4-tuple $G = (V, \Sigma, \mathcal R, S)$ where

• $V$ is a finite set of variables (or non-terminals).
• $\Sigma$ is a finite set, disjoint from $V$, of terminals.
• $\mathcal R \subseteq V \times (V \cup \Sigma)^\star$ is a finite set of rules, written $A \to w$, $w \in (V \cup \Sigma)^\star$.
• $S \in V$ is the start symbol.

• Define a binary relation $\implies$ over $(V \cup \Sigma)^\star$.
• $u A v \implies u w v$ means that $u, v \in (V \cup \Sigma)^\star$ and $A \to w \in \mathcal R$.
• Write $\stackrel{*}{\implies}$ for the reflexive and transitive closue of $\implies$ (i.e. allow any number of derivations).
• $L(G) = \{w \in \Sigma^\star \mid S \stackrel{\star}{\implies} w\}$.

It can be generated by some context-free grammar.

Every rule is of the form $R \to wT$ or $R \to w$ where $w \in \Sigma^\star$ and $R, T \in V$.

Every rule is of the form $R \to aT$, $R \to T$ or $R \to \epsilon$ where $a \in \Sigma$, $R, T \in V$. This is different because in just right-linear cases, it’s $R \to wT$ where $w \in \Sigma^\star$.

For each rule $R \to wT$ with $w = a _ 0 \cdots a _ n$, add variables $V _ 1, \ldots, V _ n$ and replace the rule with

\[R \to a_0 V_1, \quad V_1 \to a_1 V_2,\quad\ldots, \quad V_n \to a_nT\]

A language is regular if and only if it is generated by a right-linear context-free grammar.

• Underline indicates symbol we are about to replace
• Overline indicates symbol we have just replaced

They show derivations independent of the order that “disjoint” steps are applied.

They determine distinct parse trees.

A derivation in which at each step, the leftmost occuring variable is chosen for replacement.

There exists at least one string with different leftmost derivations.

In general these are undecidable.

The language can only be generated by ambiguous grammars.

Every rule has one of the forms

\[\begin{aligned} &A \to BC \\\\ &A \to a \\\\ &S \to \epsilon \end{aligned}\]

where $S$ is the start variable, and $B, C \ne S$.

Because any context-free language can be generated by a context-free grammar in Chomsky normal form.

There are 5 steps: START, TERM, BIN, DEL, UNIT (“starting term, bin the Dell unit”).

• START: Rename $S$ in the original CFG to $S _ 0$, and add the new rule $S \to S _ 0$.
• TERM: For each rule of the form $A \to X _ 1 \cdots a \cdots X _ n$, replace $a$ by the variable $N _ a$ along with the rule $N _ a \to a$. (“Nonsolitary terminals”)
• BIN: replace each rule $A \to X _ 1 X _ 2 \cdots X _ n$ with $A \to X _ 1 A _ 1$, $A _ 1 \to X _ 2 A _ 3$, etc.
• DEL: Call a variable with a rule of the form $A \to \varepsilon$ nullable, or if $A \to X _ 1 \cdots X _ n$ and each $X _ i$ are nullable, then $A$ is also nullable. In each place where a nullable variable occurs, add a new rule with that variable omitted. Then remove all the original $A \to \varepsilon$ rules.
• UNIT: Remove all unit rules $A \to B$ by adding additional rules for $A$ corresponding to the possible derivations for $B$.

Every derivation of a string of length $n$ has exactly $2n - 1$ steps.

• Yes
• Yes
• Yes
• No
• No

• $A = \{0^n 1^n 0^m \mid n, m \ge 0\}$
• $B = \{0^n 1^m 0^m \mid n, m \ge 0\}$

both context-free, but $A \cap B = \{0^n 1^n 0^n \mid n \ge 0\}$ is not.

The intersection of a context-free language with a regular-language is context-free.

Consider

\[A = \\{w w \mid w \in \\{0, 1\\}^\star\\}\]

Then $A$ is not context-free (consider the pumping lemma) but $A^{\mathsf C}$ is, since it is generated by the CFG $(\{S, A, B, C\}, \{0, 1\}, \mathcal R, S)$ where $\mathcal R$ is described by

\[\begin{aligned} S &\to A \mid B \mid AB \mid BA \\\\ A &\to CAC \mid 0 \\\\ B &\to CBC \mid 1 \\\\ C &\to 0 \mid 1 \end{aligned}\]

then this generates all strings of odd length (consider $S \to A$ or $S \to B$) and also all strings of the form $x0y u 1 v$ or $u1vx0y$ where $x, y, u, v \in \{0, 1\}^\star$ and $ \vert x \vert = \vert y \vert $, $ \vert u \vert = \vert v \vert $. This covers all strings in $A^{\mathsf C}$.

First note that any CFG is right linear if and only if it can be made strongly right-linear, where every rule is of the form $R \to aT$, $R \to T$ or $R \to \epsilon$ where $a \in \Sigma$, $R, T \in V$. This is different because in just right-linear cases, it’s $R \to wT$ where $w \in \Sigma^\star$.

So it suffices to show a language is regular iff it is generated by a strongly right-linear CFG.

Regular implies strongly right linear: Suppose we have a DFA $M = (Q, \Sigma, \delta, q _ 0, F)$ representing a regular language $L$. We can consider $G _ M = (Q, \Sigma, \mathcal R, q _ 0)$ via

\[\begin{aligned} q \to a q' \in \mathcal R &\iff \delta(q, a) = q' \\\\ q \to \epsilon \in \mathcal R &\iff q \in F \end{aligned}\]

Strongly right linear implies regular: Suppose we have a strongly right linear CFG $G = (V, \Sigma, \mathcal R, S)$. Then construct $N _ G = (V, \Sigma, \delta, S, F)$:

\[\begin{aligned} R' \in \delta(R, a) &\iff R \to aR' \in \mathcal R \\\\ R \in F &\iff R \to \epsilon \in \mathcal R \end{aligned}\]

CFGs are not closed under complement, but DPDAs are (complement of accept/reject states). So the languages recognised by a DPDA must be a strict subset of those recognised by a CFG.

\[\begin{aligned} S \to \epsilon \mid 0 \mid 1 \mid 0S0 \mid 1S1 \\\\ \end{aligned}\]

\[\begin{aligned} S &\to 0S0 \mid 1S1 \mid 0A1 \mid 1A0 \\\\ A &\to \epsilon \mid A0 \mid A1 \end{aligned}\]

The general idea: $\mathbf{NonPal} = \{0, 1\}^\star \cap \mathbf{Pal}^C$. If $x$ is an element of $\mathbf{NonPal}$, then

• $0x0$ is an element of $\mathbf{NonPal}$
• $1x1$ is an element of $\mathbf{NonPal}$

If $y$ is an element of $\{0, 1\}^\star$, then

• $0y1$ is an element of $\mathbf{NonPal}$
• $1y0$ is an element of $\mathbf{NonPal}$

\[A = \\{w w \mid w \in \\{0, 1\\}^\star\\}\]

This is not context free, but its complement is.

• $A = \{0^n 1^n 0^m \mid n, m \ge 0\}$, this is context free
• $B = \{0^n 1^m 0^m \mid n, m \ge 0\}$ , this is context free

But

\[A \cap B = \\{0^n 1^n 0^n \mid n \ge 0\\}\]

is not context-free.

Define the NPDA

\[P = (Q_1 \times Q_2, \Sigma, \Gamma, \delta, (q_1, q_2), \perp, F_1 \times F_2)\]

where $\delta$ is given by

\[\delta((r, t)), a, A) = \\{((r', t'), \alpha) \mid r' \in \delta_1(r, a), (t', \alpha) \in \delta_2(t, a, A)\\}\]

Then

\[L(P) = L(N) \cap L(M)\]

Suppose $S _ 1$ and $S _ 2$ are the start variables of two different CFGs and that the variables each CFG uses are disjoint. Then

• Union: $S \to S _ 1 \mid S _ 2$
• Concat: $S \to S _ 1 S _ 2$
• Star: $S \to S S _ 1 \mid \epsilon$

gives a CFG generating the union, concat and star respectively.

• Find grammar $G^+$ with $L(G^+) = L(G)$ such that $G^+$ has no rules of the form $A \to \epsilon$ or $A \to B$. This can be done by applying the DEL and UNIT rules from the construction of Chomsky normal form.
• Find a grammar $G’$ with $L(G’) = L(G^+)$ such that all non-terminals $A$ derive some string and each non-terminal is reachable from the start state, and the properties of $G^+$ are preserved:
  • Call a variable “useless” if it doesn’t generate any string. This can be done by marking all terminals, and then marking all variables which generated marked symbols, repeating until no new symbols are marked. If a variable was not marked in this process, it is useless.
  • Call a variable “reachable” if it is reachable from the start state. This can be done by marking the start state, then marking all derivations which contain the start state, and repeating until no new symbols are marked.
  • Then remove all useless and unreachable vertices.
• Now construct a directed graph with variables as vertices and edges from $A$ to $B$ whenever there is a rule $A \to uBv$.
• Then this graph has a cycle iff the grammar is infinite.

(From https://math.stackexchange.com/a/1891462/996278)