Chomského hierarchie

Počítačům předcházely matematické modely. Teorie automatů studuje abstraktní počítačové zařízení, nebo „stroje“. V roce 1936 Alan Turing popsal Turingův stroj. V letech 1940-1950, byly zkoumány mnoha výzkumníky jednoduché druhy automatů, které dnes nazýváme konečné automaty.

Původní cíl byl formalizovat popis přirozeného jazyka způsobem, aby mohl být automatizován překlad z jednoho přirozeného jazyka do druhého, nebo aby přirozený jazyk sloužil jako prostředek komunikace člověka s počítačem. To se ukázalo být velmi obtížné a teprve dnes se v této disciplíně dosahuje prvních výsledků.

Gramatika

Jednou z možností, jak popsat formální jazyk je použití gramatiky. Gramatika je formalismus sloužící pro generování jazyka

DEFINICE:

Gramatika G je čtveřice G = (N, Σ, P, S), kde
  • N Konečná množina neterminálů, má roli pomocných proměnných.
  • Σ Terminální symboly – konečná množina terminálů (abecedy), nad níž je definován jazyk. Terminální symbol se dál neexpandují. Musí platit Σ∩N = {}
  • P Přepisovací pravidla – je množina P z relace P ⊆ (N∪Σ)∗N(N∪Σ)∗ × (N∪Σ)∗
    tzn. prvek (α, β) ∈ P zapíšeme α → β a nazveme pravidlo.
  • S Počíteční symbol – S ∈ N je výchozí (také počáteční) symbol gramatiky

V Chomského notaci se velkými písmeny (např. S, X, Y) reprezentují neterminální (proměnné) symboly. Malé písmena (např. x, y, z) reprezentují terminály.

Teorie formálních jazyků našla uplatnění v oblasti programovacích jazyků. Backus a Nauer použili základní objekty gramatiky pro definici syntaxe programovacího jazyka Algol 60. Vytvořili speciální notaci, ve které se dá gramatika jazyku popsat: Backus-Nauerova Forma (BNF) nebo Rozšířená Backus-Nauerova forma (EBNF).

Jak to funguje:
Všimněte si, že gramatika obsahuje přepisovací pravidla P. Pokud chcete vygenerovat jazyk pomocí gramatiky G, tak začněte u počátečního symbolu S. Dále, podívejme se, jaké pravidla P obsahují startovací symbol na levé straně. Každé pravidlo popisuje povolenou derivaci řetězce. Pokud náš generovaný řetězec obsahuje neterminál, můžeme na tento neterminál aplikovat další derivaci z příslušných pravidel, dokud nedostaneme pouze řetězec terminálů (větu jazyka). Pro začátečníka je vhodné začít u regulárních jazyků.

Větná forma

Ze startovacího symbolu S se po libovolném počtu derivací bude generovat řetězec α. α ∈ (N∪Σ)∗. Větná forma je řetězec, který můžu vygenerovat ze startovacího symbolu.

Věta

Je taková větná forma, která obsahuje pouze terminální symboly α ∈ Σ∗.

Chomského klasifikace gramatik

Chomského hierarchie je hierarchie tříd formálních gramatik generujících formální jazyky. Základy teorie jazyků a gramatik položil v roce 1956 americký lingvista Noam Chomsky, Polského původu. Vymezuje čtyři typy gramatik, které se liší v podobě přepisovacího pravidla P.

Neomezená gramatika (Typ 0)

Pravidla shodná s definicí gramatiky. Na pravé straně musí být minimálně jeden neterminál a na levé, může být cokoliv.

(N∪Σ)∗N(N∪Σ)∗ → (N∪Σ)∗

Generuje rekurzivně spočetný jazyk. Výpočetní model Turingovým strojem.

Kontextová gramatika (Typ 1)

Pravidla této gramatiky implikují, že neterminál N může být nahrazen řetězcem γ pouze tehdy, je-li jeho levým kontextem řetězec α a pravým kontextem řetězec β. α, β ∈ (N∪Σ)∗, γ ∈ (N∪Σ)+

αNβ → αγβ
S → ε. S se nesmí vyskytovat na pravé straně.

Kontextové gramatiky neobsahují pravidla tvaru αNβ → αβ, tj. nepřipouštějí, aby byl neterminál nahrazen prázdným řetězcem. Jde o nezkracující gramatiku.

Generuje kontextový jazyk, rekurzivní jazyk. Rozpoznatelné lineárně omezeným Turingovým strojem.

Bezkontextové (Typ 2)

N → (N∪Σ)*

Substituce pravé strany pravidla za neterminál N lze provádět bez ohledu na kontext, ve kterém je neterminál N uložen. Na rozdíl od kontextových gramatik, bezkontextové gramatiky smí obsahovat pravidla tvaru N → ε.

Generuje bezkontextový jazyk. Rozpoznatelné zásobníkovým automatem.

Regulární (Typ 3)

{{ term regularni-gramatika }}

Generuje regulární jazyk. Výpočetní model konečným automatem.

Uzavřenost

Rekurzivně spočetné jazyky jsou uzavřené na operacích sjednocení, součin a iterace.

Kontextové jazyky jsou uzavřené na operacích sjednocení, součin, iterace a doplněk.

Věta: Třída bezkontextových jazyků je uzavřena na operacích sjednocení, součin a iterace.

K zamyšlení

Proč máme tolik druhů gramatik, když je všechny můžu generovat obecnou gramatikou?

Příklad regulárního jazyka

L = {an: n ≥ 0}

Proč není třída bezkontextových uzavřena na průnik?

Protipříklad: Mejme bezkontextový jazyk L1 = {anbncm; a,b,c ∈ Σ*, n, m }
L1 ∩ am bn cn = anbncn (kontextový)

Související