A.5 Context-free Languages, CFG and Push-down Automata
Context-free Languages (CFL) have structures which cannot be specified by regular expressions. Most of the computer programming languages are of this type. The grammar which can specify a CFL is called Context-free Grammar (CFG) and acceptor for such a language is called Push-down Automata (PDA).
A.5.1 Context-free Language
We consider first an example:
Palindrome language PAL over ∑ = {a, b} can be defined as:
- λ, a, b ∈ PAL
- ∀ S ∈ PAL, aSa, bSb ∈ PAL
- no other string in PAL unless it can be obtained by applying (1) and (2).
Typical strings in PAL are: a, b, aa, bb, aaa, aba, bab, 
,…
We can ...
Get Compilers: Principles and Practice now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
