Word (muodollinen kieli)

Muodollisen kielen sana (myös - ketju , rivi ) on mielivaltainen merkkijono annetusta aakkosesta . Sanan merkkien lukumäärää kutsutaan sen pituudeksi ja sitä merkitään . Yksittäinen sana, jonka pituus on 0, ( tyhjä sana ), joka ei sisällä merkkejä (merkitty , tai ), voidaan sallia. $\alpha$ $|\alpha |$ $e$ $\varepsilon$ $\lambda$

Aakkosten kaikkien pituisten sanojen joukkoa merkitään , äärellisissä aakkosissa tällaisten sanojen määrä on täsmälleen yhtä suuri kuin aakkosten koko potenssiin ( ). Kaikkien aakkosten sanojen joukko (mielisen pituisia) on merkitty ( Kleenen tähti ), näin: $n$ $A$ $A^{n}$ $n$ $|A^{n}|=|A|^{n}$ $A$ $A^{*}$

A^{*}=\bigcup _{n=0}^{+\infty }A^{n}.

Tietyn aakkoston yli olevilla sanoilla määritellään ketjutustoiminto , eli sanojen peräkkäinen liimaus. Kaikkien aakkosten sanojen joukko ketjutusoperaatiolla muodostaa monoidin ( free monoid ). Kaikki ei-tyhjät sanat aakkosten yli ketjutusoperaatiolla muodostavat puoliryhmän . $A$ $A$ $A$

Muodolliset kielet ja viralliset kieliopit
Yleiset käsitteet	Chomsky-hierarkia Aakkoset Sana
Tyyppi 0	Rajoittamaton kielioppi Turingin kone lueteltu kieli Ratkaiseva kieli
Tyyppi 1	Tilanneherkkä kielioppi Tilannekohtainen kieli Lineaarisesti rajattu automaatti
Tyyppi 2	Kontekstiton kielioppi Epäselvä kielioppi Kontekstiton kieli Työntöautomaatti ( deterministinen ) Kasvu Lemma Ogdenin Lemma Cookin lause
Tyyppi 3	Tavallinen kielioppi tavallinen kieli Tavallinen ilme Tilakone ( deterministinen , ei - deterministinen ) DFA-minimointi NFA:n määrittäminen Myhill-Neroden lause
jäsentäminen	LL analysaattori LR jäsentäjä Rekursiivinen laskeutumismenetelmä Kok-Younger-Kasami-algoritmi