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:

  1. λ, a, bPAL
  2. SPAL, aSa, bSbPAL
  3. 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, image,…

We can ...

Get Compilers: Principles and Practice now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.