Word (formelt sprog)

Ordet for et formelt sprog (også - kæde , linje ) er en vilkårlig sekvens af tegn fra det givne alfabet . Antallet af tegn i et ord kaldes dets længde og betegnes med . Et enkelt ord med længden 0, ( tomt ord ), der ikke indeholder nogen tegn (benævnt med eller ) kan tillades. $\alfa$ $|\alpha |$ $e$ $\varepsilon$ $\lambda$

Mængden af alle ord af længde i alfabetet er betegnet med , i det endelige alfabet er antallet af sådanne ord nøjagtigt lig med størrelsen af alfabetet i potensen ( ). Mængden af alle ord i alfabetet (af vilkårlig længde) er betegnet med ( Kleenes stjerne ), således: $n$ $EN$ $A^{n}$ $n$ $|A^{n}|=|A|^{n}$ $EN$ $A^{*}$

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

På ord over et givet alfabet defineres operationen af sammenkædning , dvs. successiv limning af ord. Mængden af alle ord i alfabetet med sammenkædningsoperationen danner en monoid ( fri monoid ). Sættet af alle ikke-tomme ord over et alfabet med sammenkædningsoperationen danner en halvgruppe . $EN$ $EN$ $EN$

Formelle sprog og formelle grammatikker
Generelle begreber	Chomsky hierarki Alfabet Ord
Type 0	Ubegrænset grammatik Turing maskine opregnet sprog Opløseligt sprog
Type 1	Kontekstfølsom grammatik Kontekstfølsomt sprog Lineært afgrænset automat
Type 2	Kontekstfri grammatik Tvetydig grammatik Kontekst frit sprog Pushdown-automat ( deterministisk ) Vækst Lemma Ogdens Lemma Cooks teorem
Type 3	Almindelig grammatik almindeligt sprog Almindelig udtryk Statsmaskine ( deterministisk , ikke- deterministisk ) DFA minimering Bestemmelse af NFA Myhill-Nerodes sætning
parsing	LL analysator LR-parser Rekursiv nedstigningsmetode Kok-Yngre-Kasami-algoritme