Context-Free Language

Context-Free Grammar

• A context-free grammar (CFG) is a formal grammar $G=(V,\Sigma ,R,S)$ in which each production rule is of the form $A\to w$, where $A\in V$ and $w\in (V\cup \Sigma {)}^{\ast }$.
• Let $G=(V,\Sigma ,R,S)$ be a CFG.
  • If $u,v,w\in (V\cup \Sigma {)}^{\ast }$ and $A\to w$ is a rule, then we say that $uAv$ yields $uwv$, written $uAv\Rightarrow uwv$
  • The language $L(G)=\{w\in {\Sigma }^{\ast }\mid S\stackrel{\ast }{\Rightarrow }w\}$ (which is the set of all strings generated by $G$) is called the language generated by $G$ and is said to be a context-free language (CFL).
  • Given a string $w\in {\Sigma }^{\ast }$:
    • A derivation of $w$ in $G$ is a sequence of substitutions of the form:
      • $S\Rightarrow u_1\Rightarrow u_2\Rightarrow \cdots \Rightarrow u_n=w$, where each $u_i$ is in $(V\cup \Sigma {)}^{\ast }$
      • If such a derivation for $w$ exists in $G$, we say that $G$ generates $w$ (or $S$ derives $w$) and write $S\stackrel{\ast }{\Rightarrow }w$
    • $w$ is said to be derived ambiguously in $G$ if it has two or more different leftmost derivations.
    • A derivation of $w$ is a leftmost derivation if at every step the leftmost remaining variable is the one replaced.
    • The following are equivalent:
      • $w\in L(G)$
      • $S\stackrel{\ast }{\Rightarrow }w$
      • There exists a parse tree for $w$ with respect to $G$
    • A parse tree for $w$ with respect to $G$ is a rooted ordered tree in which:
      • The root is labeled by the start variable $S$
      • The leaves are labeled by the symbols of $w$
      • Each internal node is labeled by a variable $A$ and has children labeled $X_1,\dots ,X_n$ if $A\to X_1\dots X_n$ is a rule in $G$
    • There is a bijection between the set of left-most derivations of $w$ and the set of parse trees for $w$ with respect to $G$.
  • $G$ is ambiguous if it generates at least one string ambiguously.
    • A CFG is ambiguous iff it generates some string with two different parse trees.
  • A CFG is in Chomsky normal form if every rule is of the form $A\to BC$, $A\to a$, or $S\to \epsilon$, where $A,B,C\in V$, $a\in \Sigma$, and $S$ is the start variable, and $B$ and $C$ are not $S$.
    • If $G$ is a CFG in Chomsky normal form, and $w\in L(G)$, then $|w|\le 2^{|h|}-1$, where $h$ is the height of the parse tree for $w$.
    • (problem 2.26) If $G$ is a CFG in Chomsky normal form, and $w\in L(G)$, where $|w|\ge 1$, then every derivation of $w$ requires exactly $2|w|-1$ steps.
    • (2.9) Every CFL is generated by a CFG in Chomsky normal form.
    • $\epsilon \in L(G)$ iff its CNF contains the rule $S\to \epsilon$.todo
• A language is said to be a context-free language (CFL) if it is generated by some CFG.
  • A CFL is inherently ambiguous if all CFGs that generate it are ambiguous.
  • Every CFL is generated by a CFG in Chomsky normal form.
  • (2.32) Every regular language is context free.
• For every language $L$, the following are equivalent:
  • $L$ is a context-free language (CFL)
  • $L$ is generated by some CFG
  • (2.20) $L$ is recognized by some PDA
  • $L$ is in Chomsky normal formtodo
• Two CFGs $G_1$ and $G_2$ are said to be equivalent if $L(G_1)=L(G_2)$.
  • Remark: There can be multiple CFGs that generate the same language, moreoever, some of these may be ambiguous while others are unambiguous.
• (2.34, Pumping lemma) If $L$ is a CFL, then there exists a number $p$ (the pumping length) such that any string $s\in L$ with $|s|\ge p$ can be written as $s=uvxyz$, where:
  • $\forall i\ge 0,u{v}^{i}x{y}^{i}z\in L$
  • $|vxy|\le p$
  • $|vy|>0$
• The class of CFLs is closed under: union, concatenation, Kleene star, reversal, and intersection with regular languages. However, it is not closed under intersection or complementation.

Pushdown Automata (PDA)

• A pushdown automaton (PDA) is a 6-tuple $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,F)$, where $Q$, $\Sigma$, $\Gamma$, and $F$ are all finite sets, and
  • $Q$ is the set of states
  • $\Sigma$ is the input alphabet
  • $\Gamma$ is the stack alphabet
  • $\delta :Q\times {\Sigma }_{\epsilon }\times {\Gamma }_{\epsilon }⟶\mathcal{P}(Q\times {\Gamma }_{\epsilon })$ is the transition function
  • $q_0\in Q$ is the start state
  • $F\subseteq Q$ is the set of accept states
• A pushdown automaton $M=(Q,\Sigma ,\Gamma ,\delta ,q_0,F)$ accepts a string $w\in {\Sigma }^{\ast }$ if there exists a sequence of states $r_0,r_1,\dots ,r_m\in Q$ and strings $s_0,,s_1,\dots ,s_m\in {\Gamma }^{\ast }$ such that:
  • $r_0=q_0$ and $s_0=\epsilon$
  • For $i=0,1,\dots ,m-1$, we have $(r_i,b)\in \delta (r_i,w_{i+1},a)$, where $s_i=at$ and $s_{i+1}=bt$ for some $a,b\in {\Gamma }_{\epsilon }$ and $t\in {\Gamma }^{\ast }$.
  • $r_m\in F$
• The set of strings accepted by $M$ is the language denoted by $L(M)$, and is called the language recognized by $M$.
• A PDA can be represented using a state diagram, where each transition is labeled by the notation "$a,b\to c$" to denote that the PDA:
  • Reads the symbol $a$ from the input (or read nothing if $a=\epsilon$)
  • Pops the symbol $b$ from the stack (or pops nothing if $b=\epsilon$)
  • Pushes $c$ onto the stack (or pushes nothing if $c=\epsilon$)

CFL to CFG

• Given a CFL $L$, we can construct a CFG $G$ such that $L(G)=L$.todo

CFL to PDA

• Given a CFL $L$, we can construct a PDA $M$ such that $L(M)=L$.todo

CFG to CNF

• (2.9) Given a CFG $G=(V,\Sigma ,R,S)$ we can construct an equivalent CFG $G^{\prime }$ in Chomsky normal form
  • Add new start variable $S_0$ and new rule $S_0\to S$
  • For each an $\epsilon$-rule, $A\to \epsilon$, where $A\ne S_0$
    • Remove $A\to \epsilon$
    • For every rule $R\to u_{1}A{u}_{2}A{u}_3\cdots u_{n-1}A{u}_n$, add the rules:
      • $R\to u_1{u}_{2}A{u}_3\cdots u_{n-1}A{u}_n$
      • $R\to u_{1}A{u}_2{u}_3\cdots u_{n-1}A{u}_n$
      • $\dots$
      • $R\to u_{1}A{u}_{2}A{u}_3\cdots u_{n-1}{u}_n$
  • For each unit rule $A\to B$
    • Remove $A\to B$
    • For each rule $B\to u$, where $u\in (V\cup \Sigma {)}^{\ast }$
      • Add the rule $A\to u$, unless this was a unit rule previously removed
  • For each rule $A\to u_1{u}_2\cdots u_k$, where $k\ge 3$ and $u_i\in V\cup \Sigma$,
    • Replace $A\to u_1{u}_2\cdots u_k$ with the rules, $A\to u_1{A}_1,A_1\to u_2{A}_2,\dots ,A_{k-2}\to u_{k-1}{u}_k$, where $A_i$‘s are new variables.
      • Repalce each terminal $u_i$ in the previous rule(s) with the new variable $U_i$ and add the rule $U_i\to u_i$

DFA to CFG

• Let $M=(Q,\Sigma ,\delta ,q_0,F)$ be a DFA. We can convert $M$ to a CFG $G=(V,\Sigma ,R,S)$ as follows:
  1. Make a variable $R_i$ for each state $q_i\in Q$
  2. Add a rule $R_i\to a{R}_j$ to the CFG if $\delta (q_i,a)=q_j$
  3. Add a rule $R_i\to \epsilon$ if $q_i\in F$
  4. Make $R_0$ the start variable of the CFG, where $q_0$ is the start state of $M$