Word (formellt språk)

Ordet för ett formellt språk (även kedja , linje ) är en godtycklig sekvens av tecken från det givna alfabetet . Antalet tecken i ett ord kallas dess längd och betecknas med . Ett enstaka ord med längden 0, ( tomt ord ), som inte innehåller några tecken (betecknat med , eller ) kan tillåtas. $\alfa$ $|\alpha |$ $e$ $\varepsilon$ $\lambda$

Mängden av alla ord av längd i alfabetet betecknas med , i det finita alfabetet är antalet sådana ord exakt lika med storleken på alfabetet i potensen ( ). Uppsättningen av alla ord i alfabetet (av godtycklig längd) betecknas med ( Kleenes stjärna ), alltså: $n$ $A$ $A^{n}$ $n$ $|A^{n}|=|A|^{n}$ $A$ $A^{*}$

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

På ord över ett givet alfabet definieras operationen för sammanlänkning , dvs successiv limning av ord. Mängden av alla ord i alfabetet med sammanlänkningsoperationen bildar en monoid ( fri monoid ). Uppsättningen av alla icke-tomma ord över ett alfabet med sammanlänkningsoperationen bildar en halvgrupp . $A$ $A$ $A$

Formella språk och formella grammatiker
Allmänna begrepp	Chomsky hierarki Alfabet Ord
Typ 0	Obegränsad grammatik Turing maskin uppräknat språk Lösbart språk
Typ 1	Sammanhangskänslig grammatik Kontextkänsligt språk Linjärt begränsad automat
Typ 2	Kontextfri grammatik Tvetydig grammatik Kontextfritt språk Pushdown-automat ( deterministisk ) Tillväxt Lemma Ogdens Lemma Cooks teorem
Typ 3	Vanlig grammatik vanligt språk Vanligt uttryck Tillståndsmaskin ( deterministisk , icke- deterministisk ) DFA-minimering Bestämning av NFA Myhill-Nerodes sats
analysera	LL analysator LR-parser Rekursiv nedstigningsmetod Kok-Yngre-Kasami-algoritm