Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky
`` `
S -> ASB | ε
`` `
Vysvetlenie:
* s: Toto je začiatočný symbol gramatiky. Predstavuje reťazec patriaci k jazyku `aⁿbⁿ`.
* a: Predstavuje doslovný znak „a“.
* b: Predstavuje doslovný znak „B“.
* |: Predstavuje „alebo“. Znamená to, že vľavo existuje viac výrobných pravidiel pre symbol.
* ε: Predstavuje prázdny reťazec.
Ako to funguje:
1. `s -> asb`: Toto pravidlo generuje „A“, po ktorom nasleduje „S“ (ktorý nakoniec vygeneruje viac „A a„ B), po ktorom nasleduje „B“. Zakaždým, keď sa toto pravidlo uplatňuje, efektívne pridáva doľava jeden „A“ a jeden „B“ doprava, pričom zachováva rovnováhu požadovanú jazykom.
2. `s -> ε`: Toto pravidlo poskytuje základný prípad rekurzie. Umožňuje ukončenie derivácie a vytvára prázdny reťazec (kde n =0).
Príklady odvodenia:
* n =0:Empty String (ε)
`S -> ε`
* n =1:"ab"
`S -> asb`
`S -> aεb`
`S -> ab`
* n =2:"aabb"
`S -> asb`
`S -> aasbb`
`S -> aAεbb`
`S -> aabb`
* n =3:"aaabbb"
`S -> asb`
`S -> aasbb`
`S -> aaasbbb`
`S -> aaAεbbb`
`S -> aaabbb`
Prečo tento CFG generuje iba aⁿbⁿ:
Jediným spôsobom, ako odvodiť reťazec z 's', je opakovane uplatňovaním pravidla `s -> nula alebo viackrát alebo viackrát, po ktorom nasleduje použitie pravidla` s -> ε` raz. Každá aplikácia `S -> ASB` pridá jeden 'A' doľava a jednu„ B “doprava. Výsledný reťazec bude preto mať vždy rovnaký počet „A a 'B's, so všetkými A predchádzajúcimi všetkým B. To presne popisuje jazyk „aⁿbⁿ`.
Kľúčové koncepty:
* bez kontextu (CFG): Formálna gramatika, v ktorej majú pravidlá výroby na ľavej strane jediný nekonečný symbol a akúkoľvek kombináciu terminálových a nekoncových symbolov na pravej strane. Aplikácia pravidla výroby nezávisí od kontextu, v ktorom sa objaví nekonečný symbol.
* Terminálové symboly: Symboly, ktoré sa objavujú v konečnom reťazci (napr. „A“, „b“).
* nekonečné symboly: Symboly, ktoré predstavujú gramatické kategórie alebo stredne pokročilé kroky v derivácii (napr. „S“).
* Štart symbol: Non-terminálny symbol, z ktorého sú odvodené všetky reťazce v jazyku (napr. „S“).
* Pravidlá výroby: Pravidlá, ktoré určujú, ako možno nekonečné symboly nahradiť inými symbolmi (napr. `S -> ASB`).
Tento CFG je klasickým príkladom, ktorý sa často používa na ilustráciu sily CFG a ich schopnosti vyjadriť jazyky, ktoré nie sú pravidelné. Jazyk „Aⁿbⁿ` je štandardným príkladom jazyka bez kontextu, ktorý nie je pravidelným jazykom.