Context-Free Language

A context-free grammar providers a simple and mathematically percise mechanism for describing the methods by which phrases in some natural language are built from smaller blocks, capturing the "block structure" of sentences in a natural way.

The formalism of context-free grammars was developed in the 1956 by Noam Chomsky.

Context-Free Grammar 擁有足夠強的表達力來表示大多數程式設計語言的語法；實際上，幾乎所有程式設計語言都是通過 Context-Free Grammar 來定義的。

相比 Context-Sensitive，正如因為規則變化時，不會因為上下文的關係而有所不同，所以才會稱呼為 Context-Free。

Context-Free Grammar

$$G=(V,\mathrm{\Sigma },R,S)$$

• $V$ is an alphabet. (Variables + Terminals)
• $\mathrm{\Sigma }$ is a subset of
  $V$, the set of terminals
• $R$ rules (aka Productions) is a finite set of mapping:
  $(V-\mathrm{\Sigma })\to V^{\star }$
• $S$ is a start variable.

String Derivation

1. Start from
   $S$.
2. Replace a non-terminal symbol of the current string with a string by applying a grammar rule:
   $A\to \beta$.

$A=$ the non-terminal and

$\beta =$ the string of

$V^{\star }$ to place

$A$.

3. Continue the derivation until string contains on non-terminal.

Example

Design a context-free grammar for this language

$L=\{a^n{b}^n\}$.

$$\begin{gathered} G=(V,\mathrm{\Sigma },R,S) \\ V=\{a,b,S\} \\ \mathrm{\Sigma }=\{a,b\} \\ R=\{S\to aSb|ab|\epsilon \} \end{gathered}$$

我們可以利用該 Grammar 來產生符合該文法的字串：

$$S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aabb$$

在產生的過程，為了跟 Grammar 上的箭頭

$\to$ 做區分，記號上會使用

$\Rightarrow$，並讀作 "yields"；而整個字串的產生過程就稱為 "String Derivation"。

Context-Free Grammar 中的 Productions 有兩種常見書寫方式，一種為 Backus-Naur Form；另一種為 Chomsky Normal Forms，各有不同的優缺點：

Backus-Naur Form

<variable> ::= <expression>

• <variable> is a non-terminal symbol.
• <expression> consists of one or more sequences of terminal and non-terminal symbol and each sequences is separated by the | symbol.
• The symbols can not appear on the left side of a production.

BNF is easily understood by humans, useful for Parser Generators, Uses LL, LR, LALR Parsing algorithms.

Chomsky Normal Forms

$S\to AB$

$A\to a$

$S$ is the start variable,

$AB$ are any two non-terminal symbol and

$a$ is a terminal.

CNF is often difficult to understand, useful for theorem proving, Uses the Cocke-Younger-Kasami Parsing algorithms.

Context-Free Languages

A languages which is generated from a Context-Free Grammar is a Context-Free Languages.

通常最好的 Context-Free Language 的範例就是 Balanced Parenthesis：

• 假設
  $V=\{S,(,)\},\mathrm{\Sigma }=\{(,)\},R=\{S\to SS,S\to (S),S\to \epsilon \}$

或是 Arithmetic Expressions（例如加法與乘法）：

$$\begin{gathered} V=\{S,E,F,+,\times ,\text{id}\}, \\ \mathrm{\Sigma }=\{+,\times ,\text{id}\}, \\ R=\{S\to E,E\to E+E,E\to F,E\to \text{id},F\to F\times F,F\to E,F\to \text{id}\} \end{gathered}$$

All Regular Languages are Context-Free Languages.
Corollary: The class of regular language is a subset of context-free language.

But, some context-free language are not regular, for example:

$L=\{a^n{b}^n\},n=\{0,1,2,\dots \}$

Parsing Tree

By following the derivation of a string, we can construct a parsing tree.

1. Root = the start variable,
   $S$
2. Replacing a variable by using a grammar rule creates a branch under it:
   • Parent Node: The variable.
   • Children: The symbols of the replacing string.
3. Node type:
   • Internal nodes = Non-terminals
   • Lead nodes = Terminals +
     $\epsilon$
4. Concatenating the leaf nodes (from the left to the right) forms the final string.

Derivations

• Left-most derivation: At each step, the left most non-terminal is replaced.
• Right-most derivation: At each step, the right most non-terminal is replaced.

Theorem: If

$w\in L(G)$,

$w$ can be generated by using left-most derivation, right-most derivation or both the methods.

Ambiguous Grammars

形容有一個字串有一個以上的 parsing tree 可以應對（在同一種 most derivation）。

A grammar is ambiguous, if there are some strings that have more than one distinct parsing tree.

Theorem: Having different derivation methods does not necessarily imply generating distinct parsing tress.

Ambiguous grammar cause that we have multiple ways to execute the program segment.

Theorem: There are some context-free languages that can only be generated by ambiguous grammars.

Inherently ambiguous

形容某一種語言用文法表示時必是 Ambiguous。

天生就存在 Ambiguous Grammars 的 Context-Free Languages，請避免設計這樣的語言，因為無解。

Example

最好的例子就是四則運算：

同樣產生出來的字串都是 "id + id * id"，但到底是先乘還是先加，在 CFG 中是沒有明確的被定義，所以這樣就是一種 Ambiguous。

Regular Grammer

A context-free grammar is right-linear, if each grammar rule is in either one of the following formats:

• $A\to \beta$
• $A\to \alpha B$.
• Where
  $\alpha$
  $\beta$ strings contain only terminals, and
  $A$ and
  $B$ are non-terminals.

A context-free grammar is left-linear if and only if all its grammar rules obey the following formats:

• $A\to \beta$
• $A\to B\alpha$.
• Where
  $\alpha$
  $\beta$ strings contain only terminals, and
  $A$ and
  $B$ are non-terminals.

Closure Properties

Closure Properties of Context-Free Language

CFL are closed under union, Kleene star, concatenation.
The intersection of a CFL and a regular language is a CFL (not regular).

Non-closure Properties of Context-Free Language

CFL are not closed under intersection, complement, difference.

Closure Properties of DCFL

DCFL are closed under complement, concatenation, Kleene star.
The intersection of a DCFL and a regular language is a DCFL (not regular).

Non-closure Properties of DCFL

DCFL are not closed under union. (common CFL)
DCFL are not closed under intersection. (non-CFL)

Definition: A context-free grammar is regular if and only if it is right(left)-linear.

Theorem: A regular grammar can be modified into a left-linear grammar.
Theorem: Regular languages are generated by regular grammars.

Example

$R=\{S\to aS|bS|abS|\epsilon \}$
So, this context-free grammar is right-linear.

Pushdown Automata

Pushdown Automata were introduced A. G. Oettinger in 1961.
The machines accepting context-free languages.

Components

• An infinite input tape: keeping input string
• A state register: inidcating machine conditions
• A control unit: deciding actions.
• A read head: reading and erasing symbols.
• A stack: 有一個 stack 的儲存空間（push、pop）

When the stack is empty, the state is in a final state, and the input tape is empty,

$M$ accepts the string.

Compare with Finite Automata

1. The PDA has a stack.
2. The stack space is unlimited.
3. The stack can store information.
4. The topmost symbols can help us in making decisions.

input:

$(q,a,\beta )=(\text{current state, current input symbol, contents on the top of stack})$

Possiable actions in one step:

1. Moving right by one position (eating a symbol).
2. Changing the current state.
3. Modifying the top contents of the stack.

An FA is a PDA without the stack, therefore FA forms a proper subset of PDA.

Configuration

The current configuration of a Pushdown Automata can be described by using:

$(q,\beta ,\gamma )$.

• $q$: current state.
• $\beta$: the remaining input string.
• $\gamma$: the string on the stack.
• _: The position of the read head.

Acceptance by PDA

A string

$w$ is accepted by PDA

$M$, if

1. $w$ is exhausted
2. $M$ is in a final state
3. The stack is empty. (optional)
4. The final configutation
   $(f,\epsilon ,\epsilon )$

Mathematical Model

A pushdown automata is sextuple representation:

$$M=(K,\mathrm{\Sigma },\mathrm{\Gamma },\mathrm{\Delta },s,F)$$

• $K$ : a finite set of states,
• $\mathrm{\Sigma }$ : an alphabet,
• $\mathrm{\Gamma }$ : an alphabet for stack symbol
• $s$ : initial state
• $F$ : set of final states.

The Transition Relation

$\mathrm{\Delta }$ transition relation:

$$\mathrm{\Delta }(q,a,\beta )\to (p,\gamma )$$

The input symbol may be

$\epsilon$; The top stack string may be

$\epsilon$.

• $p$ is next state.
• $\gamma$ is new topmost string on the stack.

A pushdown automata uses a transition relation

$\mathrm{\Delta }$ to direct its compution, it is a relation:

• May be partially defined
• May be non-deterministic
• May perform ambiguous computation

The meaning of transition rule:

$\mathrm{\Delta }(q,a,\beta )\to (p,\gamma )$

if (state == q && symbol == 'a' && top-most-stack == 'beta') {
    state = p;
    pop 'beta';
    push 'gamma'
}

PDA 一次就是 push 一層或是 pop 一層，而 push/pop 的內容可以是多個 symbol，例如 "aa"；而一般來說 stack 的最底層會是 "$" 或 "

$z_0$ "。

Language of PDA

The language accepted by a PDA

$M$ is denoted by

$L(M)$.

• If
  $w$ is NOT in
  $L(M)$
  $\to$ definitely rejected.
• If
  $w$ is in
  $L(M)$
  $\to$ May be rejected or be accepted.
  But there always exists a computation leading
  $M$ to accept
  $w$.

Context-Free Language

$L(M)$ is the set of strings

$w$ accepted by

$M$. A language

$L$ is called Context-Free Language if and only if there exists some PDA

$M$ such that,

$L=L(M)$.

Pushdown Automata: Language recognizer.
Context-Free Grammar: Language generator.

Transition Diagram

意思是從狀態

$q$ 到狀態

$p$ ，必須要讀取到字符

$a$，且 stack pop 為

$b$，然後 push

$c$。

Example

$L=\{a^n{b}^n:n\ge 0\}$, Design a Pushdown Automata for this language:

$M=(K,\mathrm{\Sigma },\mathrm{\Gamma },\mathrm{\Delta },s,F)$, and:

$K=\{q_0,q_1,q_2,q_3\}$、

$\mathrm{\Sigma }=\{a,b,\epsilon \}$,

$\mathrm{\Gamma }=\{a,\epsilon ,z_0\}$,

$s=q_0$,

$F=\{q_3\}$ and the

$\mathrm{\Delta }$ transition relation:

$q$	$a$	$\beta$	$\mathrm{\Delta }(q,a,\beta )$
$q_0$	$\epsilon$	$\epsilon$	$(q_1,z_0)$
$q_1$	$a$	$\epsilon$	$(q_1,a)$
$q_1$	$\epsilon$	$\epsilon$	$(q_2,\epsilon )$
$q_2$	$b$	$a$	$(q_2,\epsilon )$
$q_2$	$\epsilon$	$z_0$	$(q_3,\epsilon )$

該語言為:

$\{\epsilon ,ab,aabb,aaabbb,aaaabbbb,...\}$

若畫圖為：

Non-Determinstic Pushdown Automata

A Pushdown Automata is non-determinisitc in nature, because the partially defined

$\mathrm{\Delta }$ transition relations.

Definition: If and only if there exists a sequence of transitions leading

$M$ into a final configuration.

Example

There is a language

$L=\{w{w}^R,w\in {\mathrm{\Sigma }}^{\star }\}$,

$\mathrm{\Sigma }=\{a,b\}$. 這種語言只存在 Non-determinstic 版本的 PDA

$M$，其定義如下：

$$\begin{gathered} M=(K,\mathrm{\Sigma },\mathrm{\Gamma },\mathrm{\Delta },s,F) \\ K=\{s,f\},F=\{f\},\mathrm{\Sigma }=\mathrm{\Gamma }=\{a,b\} \\ \mathrm{\Delta }=\{ \\ (s,a,\epsilon )\to (s,a) \\ (s,b,\epsilon )\to (s,b) \\ (s,\epsilon ,\epsilon )\to (f,\epsilon ) \\ (f,a,a)\to (f,\epsilon ) \\ (f,b,b)\to (f,\epsilon ) \\ \} \end{gathered}$$
其中

$(s,\epsilon ,\epsilon )\to (f,\epsilon )$ 這一條是 non-derminstic 的關鍵，它表達為：「在不讀任何 symbol 且不參考及 pop 任何 stack 情況下改變狀態」，這個步驟是很不穩定的，有可能你的

$w$ 字串，假設長度是 20，所以對半切應該要在第 20 個時走這一個規則，但是有可能在讀到第 5 個字符時就跳到

$f$ 狀態，這樣就會讓原本應該要是屬於該語言的字串被誤判為不存在；不過因為是存在一種機率這個是可以判定正確，所以這樣的設計是合法的。

Configurations

Try "aabbaa":

$$\begin{gathered} (s,"\underset{―}{a}abbaa",\epsilon )\to \\ (s,"\underset{―}{a}bbaa","\underset{―}{a}")\to \\ (s,"\underset{―}{b}baa","\underset{―}{a}a")\to \\ (s,"\underset{―}{b}aa","\underset{―}{b}aa")\to \\ (f,"\underset{―}{b}aa","\underset{―}{b}aa")\to \\ (f,"\underset{―}{a}a","\underset{―}{a}a")\to \\ (f,"\underset{―}{a}","\underset{―}{a}")\to \\ (f,\epsilon ,\epsilon ) \end{gathered}$$

Determinstic Pushdown Automata

Definition:

$M$ is a Deterministic Push Down Automata, if it satisfies the following condition:
For each configuration of

$M$, there is exactly one configuraion can succeed it.

NPDA 在實務上太難達成了（因為猜錯的機率太大），所以 DPDA 比較能符合在實務上的機械實現。

Constraints on the transition relation

$\mathrm{\Delta }(q,a,X)$:

• $\mathrm{\Delta }(q,a,X)$ appear at most once in the left side.
• If
  $\mathrm{\Delta }(q,a,X)$ exists for some
  $a\in \mathrm{\Sigma }$, there is no transition rule for
  $\mathrm{\Delta }(q,\epsilon ,X)$.

The computation of a DPDA

$M$ is controlled by a transition relation, not a function:

• $\mathrm{\Delta }$ is partially defined, though it is un-ambiguous.
• $M$ may enter infinite loops in processing strings.

有存在一種方法讓無窮迴圈去掉，讓字串讀完且停在非 final 的 state 上，讓 PDA 在實務上實現成為可能。

Acceptance by DPDA

• The input string is exhausted.
• The DPDA is in a final state.
• The stack may be non-empty.

Need to signal the end of the input string and the bottom of the stack.

1. 可以在字串結尾加上記號，例如
   $z\to (\mathrm{\#}wz\mathrm{\#})$.
2. 一開始 stack 就 push $，來做記號代表為 stack 的最底層。
3. 使用這些方法所產生的語言會跟沒使用這些方法的語言是截然不同的。

Determinstic Context-Free Language

Most computer programming languages are DCFL.
DCFL can be pared by LR(k) parser in

$O(n)$, In General CFL can be parsed within

$O(n^3)$.

The equivalence problem of two DCFL is solvable: DCFL

$L_1=L_2$.

• For CFL this problem is unsolvable.

Closure Properties

DCFL is closed under complement.

• If
  $L$ is a DCFL, so is its complement
  $L^{\prime }$.

Unambiguous CFG

Theorem: If

$L$ is a DCFL,

$L$ can be generated by an unambiguous CFG.

Unambiguous CFG 不一定是 Deterministic CFL。
Theorem: Deterministic Context-Free Language form a proper subset of Context-Free Language.

However, Deterministic Context-Free Language is still a proper super-set of regular languages.

Non-Context Free Language

Pumping Lemma

Given a context-free language

$L$, there exists

$n\ge 1$ (called a "pumping length"), such that:
For any string

$w\in L$ with

$|w|\ge n$,

$w$ can be split into

$u$,

$v$,

$x$,

$y$ and

$z$, such that:

1. $w=uvxyz$
2. $|vxy|\le n$
3. $|vy|\ge 1$
4. $u{v}^{i}x{y}^{i}z\in L$,
   $\mathrm{\forall }i\in \{0,1,2,...\}$

Ogden's Lemma

Aka. strong version of classic pumping lemmaf for context-free languages.

Given a context-free language

$L$,

$\mathrm{\exists }$

$p$ such that for any string

$w\in L$ with

$|w|\ge p$ and every way of "marking"

$p$ or more of the symbols in

$w$. The string

$w$ can be written as

$w=uvxyz$.

With strings

$u$,

$v$,

$x$,

$y$ and

$z$, such that:

1. $vy$ has at least one marked symbol.
2. $vxy$ has at most
   $p$ marked symobls
3. $u{v}^{i}x{y}^{i}z\in L$,
   $\mathrm{\forall }i\in \{0,1,2,...\}$

Reference

https://math.stackexchange.com/questions/217741/how-do-i-show-language-of-prime-number-of-xs-not-context-free
https://cs.stackexchange.com/questions/140991/proof-that-aibjck-mid-i-j-k-in-mathbbn-ikj-is-not-context-free-usi
https://cs.stackexchange.com/questions/64056/prove-if-l-0m1n-mid-m-neq-n-is-regular-or-not/64074#64074
https://cs.stackexchange.com/questions/150051/is-anbmck-n-neq-m-and-m-neq-k-context-free

tags: 計算理論