This is an old revision of the document!
2 Grammars as a Generating Device
2.3.5 Conclusion
| Chomsky type | Grammar type | Most complicated data structure |
|---|---|---|
| 0 / 1 | PS / CS | production dag |
| 2 | CF | production tree |
| 3 | FS | production list |
| 4 | FC | production element |
2.4 Actually Generating Sentences from a Grammar
generate $a^nb^nc^n$ grammar from using
1. Ss -> abc | aSQ
2. bQc -> bbcc
3. cQ -> Qc
This way of doing things is called breadth-first production; computers are better at it than people.
The CF Case
S = N | L, '&', N ;
N = 't' | 'd' | 'h' ;
L = N, ',', L | N ;
root1