Chomsky hierarchy

Chomsky hierarchy (tsz. Chomsky hierarchies)

1. (informatika) A Chomsky-hierarchia a formális nyelvek osztályozására szolgáló elméleti keretrendszer, amelyet Noam Chomsky amerikai nyelvész és logikus vezetett be 1956-ban. Ez az osztályozás négy fő nyelvosztályt különböztet meg az alapján, hogy milyen típusú grammatikaikák képesek az adott nyelvet leírni, illetve milyen automaták képesek felismerni azokat. A hierarchia a nyelvek generatív erejének növekvő sorrendjét mutatja.

• Legszűkebb osztály.
• Olyan nyelvek, amelyeket reguláris grammatika vagy véges automata ír le.
• Alakjuk:
  • Bal-lineáris: A → aB
  • Jobb-lineáris: A → Ba vagy A → a
• Nincs memória – csak aktuális állapot alapján dönt.

• Determinista véges automata (DFA)
• Nem-determinista véges automata (NFA)

• Az összes olyan szó, ami csak 0 és 1 karaktereket tartalmaz, és páros számú 0 van benne.
• Reguláris kifejezések által leírható nyelvek (pl. grep, regex).

• Az ilyen nyelveket kontextusfüggetlen grammatikák (CFG) generálják.
• A szabályok bal oldala mindig egyetlen nemterminális:
  • A → γ (γ: tetszőleges karakterlánc terminálisokból és nemterminálisokból)

• Nem-determinista veremautomata (NPDA) (Memória: verem, amely visszalépéseket tesz lehetővé)

• Kiegyensúlyozott zárójelek: pl. (()())
• Programnyelvek szintaktikus elemzése (pl. if-else szerkezetek)
• Palindrómák: wwᵣ, ahol wᵣ a w tükörképe

• A nyelvfordítók szintaktikai elemzői legtöbbször CFG-re épülnek.

• A szabályok formája: αAβ → αγβ, ahol:
  • α és β lehetnek tetszőleges sztringek (környezet),
  • A egy nemterminális, γ nem lehet üres.
• A szabály alkalmazhatósága függ a környezetétől.

• Lineárisan korlátozott Turing-gépek (LBA) (Turing-gép, amely nem használ több helyet, mint a bemenet hossza)

• aⁿbⁿcⁿ nyelv, ahol n ≥ 1 – nem kontextusfüggetlen, de kontextusfüggő
• A nyelvek, amelyek szintaktikailag érzékenyek a változó helyzetére.

• Ritkán használják a gyakorlatban, de fontos a számításelmélet szempontjából.

• Legáltalánosabb osztály.
• Tetszőleges szabály alkalmazható:
  • α → β, ahol α tartalmaz legalább egy nemterminálist.
• A nyelvekben minden, amit egy Turing-gép fel tud ismerni, ide tartozik.

• Turing-gép (determinista vagy nem-determinista) (Képes olvasni, írni, mozogni és megállni)

• Összetett számításokkal leírható nyelvek, pl. L = {⟨M, w⟩ | M elfogadja w-t}

• Nem minden Típus-0 nyelv dönthető – a megállási probléma például eldönthetetlen.

Reguláris ⊂ Kontextusfüggetlen ⊂ Kontextusfüggő ⊂ Rekurzívan enumerálható

Minden magasabb szint általában tartalmazza az alatta lévőt, de nem ekvivalens vele. Például minden reguláris nyelv kontextusfüggetlen, de nem minden kontextusfüggetlen nyelv reguláris.

1. Elméleti számítástudomány:
   • Alapja a számítási modellek összehasonlításának.
   • Eldönthetőségi és komplexitáselméleti kutatások alapját képezi.
2. Nyelvészet:
   • Chomsky eredetileg a természetes nyelvek formális modellezéséhez vezette be.
   • Megmutatta, hogy a természetes nyelv nem mindig írható le egyszerűen reguláris nyelvtannal.
3. Fordítóprogramok:
   • A nyelvi szintekhez különböző parser algoritmusok tartoznak:
     • Reguláris nyelvekhez: finite state scanner
     • Kontextusfüggetlen nyelvekhez: LL, LR, CYK algoritmusok
4. Gyakorlati alkalmazás:
   • Regex-ek → reguláris nyelvek
   • Nyelvi elemzés → kontextusfüggetlen nyelvek
   • Formális verifikáció és bizonyítás → Turing-gépek, típus-0 nyelvek

A Chomsky-hierarchia egy négy szintből álló elméleti modell, amely osztályozza a formális nyelveket aszerint, milyen szabályokkal generálhatók és milyen automaták képesek azokat felismerni:

• Típus-3: Egyszerű szabályok, gyors feldolgozás, regexek, véges állapotú automaták.
• Típus-2: Több struktúra, pl. programnyelvek, veremmemória szükséges.
• Típus-1: Környezetérzékeny szabályok, bonyolultabb nyelvek.
• Típus-0: Teljes Turing-teljesség, minden, amit géppel fel lehet ismerni.

Ez a hierarchia alapvető szerepet játszik a számításelméletben, a programnyelvek elméletében, valamint a formális nyelvészetben, és segít megérteni, hogy milyen típusú problémák oldhatók meg algoritmikusan, illetve melyek nem.

• Chomsky hierarchy - Szótár.net (en-hu)
• Chomsky hierarchy - Sztaki (en-hu)
• Chomsky hierarchy - Merriam–Webster
• Chomsky hierarchy - Cambridge
• Chomsky hierarchy - WordNet
• Chomsky hierarchy - Яндекс (en-ru)
• Chomsky hierarchy - Google (en-hu)
• Chomsky hierarchy - Wikidata
• Chomsky hierarchy - Wikipédia (angol)