Deterministická bezkontextová gramatika
V lingvistice a informatice označuje pojem deterministická bezkontextová gramatika (DCFG) vlastní podmnožinu bezkontextových gramatik takových, které rozpoznává deterministický zásobníkový automat.
Ke každé bezkontextové gramatice lze sestrojit zásobníkový automat, který reprezentuje syntaktický analyzátor pro věty generované danou gramatikou. Z hlediska aplikací teorie formálních jazyků v překladačích jsou důležité právě deterministické bezkontextové jazyky (jazyky popsané deterministickou bezkontextovou gramatikou), které lze analyzovat deterministickými syntaktickými analyzátory.[1]
Související články
Reference
- ↑ Česka: Teoretická informatika – 5.4 Deterministický zásobníkový automat
| Teorie automatů: formální jazyky a formální gramatiky | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Každá úroveň jazyků je podmnožinou své nadřazené úrovně. – Každý automat a každá gramatika má svůj ekvivalent v nadřazené úrovni. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
