Szó (formális nyelv)

A formális nyelv szava (szintén - lánc , sor ) az adott ábécé tetszőleges karaktersorozata . A szóban lévő karakterek számát hosszának nevezzük, és jelöli . Egyetlen 0, ( üres szó ) hosszúságú szó megengedett, amely nem tartalmaz semmilyen karaktert (jelölése , vagy ). $\alpha$ $|\alpha |$ $e$ $\varepsilon$ $\lambda$

Az ábécében az összes hosszúságú szó halmazát jelöli , a véges ábécében az ilyen szavak száma pontosan megegyezik az ábécé méretével a hatványra ( ). Az ábécé összes (tetszőleges hosszúságú) szavának halmazát ( Kleene csillaga ) jelöljük , így: $n$ $A$ $A^{n}$ $n$ $|A^{n}|=|A|^{n}$ $A$ $A^{*}$

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

Egy adott ábécé feletti szavakon az összefűzés művelete van definiálva, azaz a szavak egymás utáni ragasztása. Az ábécé összes szó halmaza az összefűzési művelettel monoidot alkot ( szabad monoid ). Az összes nem üres szó halmaza egy ábécén belül az összefűzési művelettel egy félcsoportot alkot . $A$ $A$ $A$

Formális nyelvek és formális nyelvtanok
Általános fogalmak	Chomsky-hierarchia Ábécé Szó
Típus 0	Korlátlan nyelvtan Turing gép felsorolt nyelv Feloldható nyelv
1. típus	Környezetérzékeny nyelvtan Környezetérzékeny nyelv Lineárisan korlátos automata
2. típus	Kontextus mentes nyelvtan Kétértelmű nyelvtan Kontextus mentes nyelv Lenyomó automata ( determinisztikus ) Növekedési Lemma Ogden Lemma Cook-tétel
3. típus	Szabályos nyelvtan szabályos nyelv Reguláris kifejezés Állapotgép ( determinisztikus , nem determinisztikus ) DFA minimalizálás Az NFA meghatározása Myhill-Nerode tétel
elemzése	LL analizátor LR elemző Rekurzív süllyedés módszere Kok-Younger-Kasami algoritmus