Klasyfikacja Chomsky’ego

W tym rozdziale poznasz cztery klasy języków formalnych wprowadzone przez Noama Chomsky’ego.

W jaki sposób stwierdzić,czy jakieś słowo należy do języka opisywanego przez daną gramatykę? Niestety nie istnieje ogólna metoda,która pozwoliłaby to zbadać dla każdej gramatyki. Dlatego w praktyce używa się wybranych klas gramatyk,dla których istnieje możliwość przeprowadzenia takiej weryfikacji. Najbardziej rozpowszechniona jest klasyfikacja gramatyk i języków wprowadzona przez Noama Chomsky’ego,która dzieli gramatyki na cztery klasy:

  • Gramatyki rekurencyjnie przeliczalne –rozpoznawane jest przez maszyny Turinga
  • Gramatyki kontekstowe –rozpoznawalne przez automaty liniowo ograniczone
  • Gramatyki bezkontekstowe –rozpoznawalne przez automaty ze stosem
  • Gramatyki regularne –rozpoznawalne przez automaty skończone

Dla ciekawych

Noam Chomsk’y to jeden z najbardziej znanych i najczęściej cytowanych profesorów lingwistyki. Wraz z Morrisem Halle opracował pojęcie gramatyki transformacyjno-generatywnej,która ma wyjaśniać kompetencje osoby mówiącej (słuchającej) w zakresie tworzenia i rozumienia wypowiedzeń danego języka. Chomsky znany jest również ze swoich radykalnych poglądów politycznych.

0 –gramatyki rekurencyjnie przeliczalne

Język rekurencyjnie przeliczalny to język,dla którego istnieje gramatyka typu 0,której produkcje są postaci α → β,gdzie α i β są dowolnymi słowami.

Dla ciekawych

Istnieje kilka równoważnych definicji języka rekurencyjnie przeliczalnego:

  1. Rekurencyjnie przeliczalny podzbiór zbioru wszystkich słów nad danym alfabetem.
  2. Język formalny,dla którego istnieje maszyna Turinga lub inna funkcja obliczalna,która jest w stanie ponumerować wszystkie słowa języka.
  3. Język formalny L,dla którego problem czy słowo x ∈ L

Gramatyki klasy 0 są zbyt ogólne do opisu składni języków programowania i języków naturalnych.

1 –Gramatyki kontekstowe

Język kontekstowy to język,który można wygenerować za pomocą gramatyki kontekstowej,której produkcje są postaci α A β → α γ β,gdzie α i β są dowolnymi słowami,A symbolem nieterminalnym,γ –niepustym słowem.

Przykład:

AB → CDB
AB → CdEB
ABcd → abCDBcd
B → b

2 –Gramatyki bezkontekstowe

Język bezkontekstowy to język,który można wygenerować za pomocą gramatyki bezkontekstowej,która po lewej stronie reguł produkcji ma pojedynczy symbol nieterminalny,po prawej zaś dowolne słowa. Postać:A → γ

Przykład:

A → aBc

Większość języków programowania należy do klasy 2.

3 –gramatyki regularne

Język regularny to język,który można wygenerować za pomocą gramatyki liniowej – takiej,która po lewej stronie reguł ma pojedynczy symbol nieterminalny,po prawej zaś słowa zawierające co najwyżej jeden symbol nieterminalny.
Przykład:

A → ε
A →  a
A →  abc
A →  B
A →  abcB

Gramatyki regularne odgrywają bardzo ważną rolę w teorii języków i teorii automatów. Napis generowany przez gramatykę regularną jest akceptowany przez automat skończony,i na odwrót.

Dla ciekawych
Jeżeli L1 oraz L2 są regularne,to regularnymi są także następujące języki:

L1 ∪ L2
L1 ∩ L2
L1 *  L2 ={xy:x ∈ L1 ∧ y ∈ L2}
L* ={ε} ∪ L ∪ L2 ∪ …

Pytania sprawdzające

  • Jak wygląda klasyfikacja gramatyk wprowadzona przez Chomsky’ego?
  • Która klasa gramatyk odpowiada maszynom Turinga?

Jeżeli masz wątpliwości,zapoznaj się jeszcze raz z powyższymi informacjami.