Frázová gramatika: Rozdiel medzi revíziami

 

Keďže frázová gramatika ako taká má konečný zápis (hoci reprezentuje potenciálne nekonečný objekt -- jazyk), všetkých frázových gramatík je [[spočíteľná množina|spočítateľne veľa]], z čoho vyplýva, že k veľkej väčšine jazykov sa nedá nájsť príslušná frázová gramatika, ktorá ich generuje. Tieto jazyky sú však veľmi komplikované a vykazujú istú "nepredstaviteľnosť". Príkladom jazykov, ktoré nie sú rekurzívne vyčísliteľné, sú [[komplement]] [[diagonálny jazyk|diagonálneho jazyka]] či komplement [[univerzálny jazyk|univerzálneho jazyka]].

 

[[Category:Formálne jazyky a automaty]]