To summarize: Context free languages (CFLs) can be described by a context free grammar (CFG) and can be processed by a pushdown automaton.
We will he only show how to construct a PDA from a grammar - the other direction is shown in the text book (6.3.2, pp. 241).
Given a CFG
, we define a PDA
![]() |
![]() |
|
![]() |
||
![]() |
||
![]() |
||
![]() |
||
![]() |
Take as an example
where
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
![]() |
|
![]() |
|
![]() |
|
![]() |
|
![]() |
|
![]() |
|
![]() |
|
![]() |
How does the accept
?
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
|
![]() |
![]() |
This example hopefully already illustrates the general idea:
![]() |
|
![]() |
|
![]() |
|
![]() |
|
![]() |
|
![]() |
The automaton we have constructed is very non-deterministic: Whenever we have a choice between different rules the automaton may silently choose one of the alternative.