Dvouúrovňová gramatika

Dvouúrovňová gramatika je formální gramatika , která se používá ke generování jiné formální gramatiky, například gramatiky s nekonečnou sadou pravidel. Takto byla van Wiingaardenova gramatika použita k definování jazyka Algol-68 . Bezkontextová gramatika , která definuje pravidla pro jinou gramatiku, může dát vzniknout v podstatě nekonečnému souboru odvozených gramatických pravidel. Díky tomu jsou dvouúrovňové gramatiky výkonnější než jednoúrovňové bezkontextové gramatiky, protože bylo prokázáno, že dvouúrovňové generativní gramatiky jsou Turingovy úplné. [jeden]

Dvouúrovňová gramatika může být také označována jako formální gramatika pro dvouúrovňový formální jazyk, tj. jazyk definovaný na dvou úrovních, jako je úroveň slova a úroveň věty.

Příklad

Známým nekontextovým jazykem je

\{a^{n}b^{n}a^{n}|n\geq 1\}.

Dvouúrovňovou gramatikou pro to může být metagramatika

N ::= 1 | N1 X ::= a | b | C

spolu s gramatikou

Start ::=

\langle a^{N}\rangle \langle b^{N}\rangle \langle c^{N}\rangle

\langle X^{N1}\rangle

::=

\langle X^{N}\rangle X

\langle X^{1}\rangle

::= X

Odkazy

↑ Sintoff, M. "Existence Van Wijngaardenovy syntaxe pro každou rekurzivně vyčíslitelnou množinu." Annales de la Société Scientifique de Bruxelles 2 (1967), 115-118.