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.
root1