Gramatică pe două niveluri
O gramatică cu două niveluri este o gramatică formală care este folosită pentru a genera o altă gramatică formală, cum ar fi una cu un set infinit de reguli. Așa a fost folosită gramatica lui van Wiingaarden pentru a defini limba Algol-68 . O gramatică fără context care definește reguli pentru o altă gramatică poate da naștere la un set esențial infinit de reguli gramaticale derivate. Acest lucru face gramaticile cu două niveluri mai puternice decât gramaticile cu un singur nivel fără context, deoarece gramaticile generative pe două niveluri s-au dovedit a fi complete la Turing. [unu]
O gramatică cu două niveluri poate fi denumită și gramatică formală pentru un limbaj formal cu două niveluri, adică o limbă definită la două niveluri, cum ar fi un nivel de cuvânt și un nivel de propoziție.
Exemplu
Un limbaj bine-cunoscut fără context este
Gramatica cu două niveluri pentru aceasta poate fi metagramatica
N ::= 1 | N1 X ::= a | b | cîmpreună cu gramatica
Începe ::= ::= ::= X
Link -uri
- ↑ Sintoff, M. „Existența sintaxei lui Van Wijngaarden pentru fiecare set recursiv enumerabil”. Annales de la Société Scientifique de Bruxelles 2 (1967), 115-118.