Palabra (lenguaje formal)

La palabra de un lenguaje formal (también - cadena , línea ) es una secuencia arbitraria de caracteres del alfabeto dado . El número de caracteres en una palabra se denomina longitud y se denota por . Se puede permitir una sola palabra de longitud 0 ( palabra vacía ), que no contenga ningún carácter (indicado por , o ). $\alfa$ ${\ estilo de visualización | \ alfa |}$ $mi$ $\varepsilon$ $\lambda$

El conjunto de todas las palabras de longitud en el alfabeto se denota por , en el alfabeto finito el número de tales palabras es exactamente igual al tamaño del alfabeto elevado a la potencia ( ). El conjunto de todas las palabras del alfabeto (de longitud arbitraria) se denota por ( estrella de Kleene ), así: $norte$ $A$ ${\ estilo de visualización A ^ {n}}$ $norte$ $|A^{n}|=|A|^{n}$ $A$ $un^{*}$

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

Sobre palabras sobre un alfabeto dado , se define la operación de concatenación , es decir, pegado sucesivo de palabras. El conjunto de todas las palabras del alfabeto con la operación de concatenación forma un monoide ( free monoid ). El conjunto de todas las palabras no vacías sobre un alfabeto con la operación de concatenación forma un semigrupo . $A$ $A$ $A$

Lenguajes formales y gramáticas formales
Conceptos generales	Jerarquía de Chomsky Alfabeto Palabra
tipo 0	Gramática ilimitada máquina de Turing lenguaje enumerado Lenguaje resoluble
Tipo 1	Gramática sensible al contexto Lenguaje sensible al contexto Autómata linealmente acotado
Tipo 2	gramática libre de contexto gramática ambigua lenguaje libre de contexto Autómata pushdown ( determinista ) Lema de crecimiento Lema de Ogden teorema de Cook
Tipo 3	gramática regular lenguaje normal Expresión regular Máquina de estados ( determinista , no determinista ) minimización de DFA Determinación de NFA Teorema de Myhill-Nerode
analizando	analizador LL analizador LR Método de descenso recursivo Algoritmo Kok-Younger-Kasami