Notes - Models of Computation MT23, Context-free grammars
Flashcards
Can you define a context-free grammar?
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.
Given a CFG $G = (V, \Sigma, \mathcal R, S)$, can you define the language generated by $G$?
- 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\}$.
What does it mean for a language to be context-free?
It can be generated by some context-free grammar.
What does it mean for a language to be right-linear?
Every rule is of the form $R \to wT$ or $R \to w$ where $w \in \Sigma^\star$ and $R, T \in V$.
What does it mean for a language to be strongly right-linear, and how is this different from being just right-linear?
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$.
Quickly prove that every right-linear CFG is equivalent to a strongly right-linear one.
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\]Can you give the characterisation of regular languages in terms of right-linear context-free grammars?
A language is regular if and only if it is generated by a right-linear context-free grammar.
Suppose we have the derivation
\[\begin{aligned}
S &\implies \underline S \, S \\\\
&\implies \overline{(\underline S)} \, S \\\\
&\implies \cdots
\end{aligned}\]
Can you explain the meaning of the $\underline{\text{underline}\,}$ and the $\overline{\text{overline}\,}$?
- Underline indicates symbol we are about to replace
- Overline indicates symbol we have just replaced
Why, in relation to context-free grammars, are parse trees useful?
They show derivations independent of the order that “disjoint” steps are applied.
What does it mean for two derivations to be “essentially different”?
They determine distinct parse trees.
What is a leftmost derivation?
A derivation in which at each step, the leftmost occuring variable is chosen for replacement.
What does it mean for a CFG to be ambiguous?
There exists at least one string with different leftmost derivations.
Why is proving that a CFG is ambigious, or that two CFGs are equivalent, difficult questions to answer?
In general these are undecidable.
What does it mean for a language to be inherently ambiguous?
The language can only be generated by ambiguous grammars.
What does it mean for a CFG to be in Chomsky normal form?
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$.
Why is Chomsky normal form, i.e. that any rule can be written
\[\begin{aligned}
&A \to BC \\\\
&A \to a \\\\
&S \to \epsilon
\end{aligned}\]
where $S$ is the start variable, and $B, C \ne S$, called Chomsky “normal” form?
Because any context-free language can be generated by a context-free grammar in Chomsky normal form.
A CFG is said to be in Chomsky normal form if all of its production rules are of the form:
\[\begin{aligned}
&A \to BC \\\\
&A \to a \\\\
&S \to \varepsilon
\end{aligned}\]
Quickly outline the procedure used to convert a general CFG to 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$.
What is the key advantage of Chomsky normal form?
Every derivation of a string of length $n$ has exactly $2n - 1$ steps.
For each of the following operations, are context-free languages closed under that operation?
- Union
- Concatenation
- Star
- Complement
- Intersection
- Yes
- Yes
- Yes
- No
- No
Quickly prove that context-free languages are not closed under intersection.
- $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.
Under what conditions is the intersection of context-free languages also context-free?
The intersection of a context-free language with a regular-language is context-free.
Quickly prove that context-free languages are not closed under complementation.
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}$.
A CFG is called right-linear if every rule is of the form $R \to wT$ or $R \to w$ where $w \in \Sigma^\star$ and $R, T \in V$.
Quickly prove that a language $L$ is regular if and only if it is generated by a right-linear CFG $(V, \Sigma, \mathcal R, S)$.
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}\]Given a vague statement like
Show that there is a context-free language that is not accepted by any DPDA
you could either try and find a particular example or use a more abstract argument. What turns out to be the trick here?
Show that there is a context-free language that is not accepted by any DPDA
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.
Give a context free grammar for $\mathbf{Pal}$, the set of palindromes over $\{0, 1\}$.
Give a context free grammar for $\mathbf{NonPal}$, the set of non-palindromes over $\{0, 1\}$.
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}$
What language is used to show that CFGs are not closed under complement?
This is not context free, but its complement is.
What languages can be used to show that context-free languages are not closed under intersection?
- $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.
Quickly give the construction used to show that the intersection of a context-free language given by an NPDA
\[N = (Q_2, \Sigma, \Gamma, \delta_2, q_2, \perp, F_2)\]
with a regular language given by a DFA
\[M = (Q_1, \Sigma, \delta_1, q_1, F_1)\]
is also 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)\]Prove that context-free languages are closed under the regular operations: union, concat and star.
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.
Quickly describe an algorithm that can be used to determine whether some CFG $G$ is infinite.
- 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)