Lenguaje normal

Un lenguaje regular ( conjunto regular ) en la teoría de los lenguajes formales es un conjunto de palabras que reconoce algún autómata finito . Es conveniente estudiar la clase de conjuntos regulares como un todo, y los resultados obtenidos son aplicables a una gama bastante amplia de lenguajes formales.

Definición

Sea un alfabeto finito . Los idiomas regulares en el alfabeto son conjuntos de palabras definidas por inducción de la siguiente manera: $\Sigma$ $\Sigma$

El conjunto vacío ( ) es un lenguaje regular. $\varnada$
Un conjunto que consta de una sola cadena vacía ( ) es un lenguaje normal. ${\displaystyle \{\varepsilon\))$
El conjunto que consta de una palabra de una sola letra ( , donde ) es un lenguaje regular. ${\ estilo de visualización \ {a \}}$ ${\ estilo de visualización \ en \ Sigma}$
Si y son lenguajes regulares, entonces su unión ( ), concatenación ( ) y tomar la estrella Kleene ( ) también son lenguajes regulares. $\alfa$ $\beta$ ${\ estilo de visualización \ alfa \ taza \ beta}$ ${\ estilo de visualización \ alfa \ beta}$ ${\ estilo de visualización \ alfa ^ {*}}$
No hay otros idiomas regulares.

Conexión entre autómatas y lenguajes regulares

El teorema de Kleene establece que la clase de lenguajes regulares es la misma que la clase de lenguajes reconocidos por un autómata finito . Esto significa que para cualquier máquina de estados finitos, el conjunto de palabras que permite es un lenguaje regular. Y viceversa, para cualquier idioma normal existe un autómata que permite palabras de ese idioma y solo de ellas.

Un subconjunto reconocible de un monoide

Este concepto se puede generalizar a un monoide arbitrario. Se dice que un subconjunto L de un monoide M es reconocible sobre M si existe un autómata finito sobre M que acepta L. Un autómata finito sobre M es un autómata que toma elementos de M como entrada . La familia de subconjuntos reconocibles de un monoide M generalmente se denota [1] . $\mathrm {Rec} (M)$

Entonces, si M es un monoide libre sobre el alfabeto , entonces la familia es simplemente una familia de lenguajes regulares . $\Sigma^{*}$ $\Sigma$ $\mathrm {Rec} \left(\Sigma ^{*}\right)$ $\mathrm {Reg} \left(\Sigma ^{*}\right)$

Véase también

Propiedad cerrada de los lenguajes regulares.

Notas

↑ Jean-Eric Pin, Mathematical Foundations of Automata Theory Archivado el 10 de septiembre de 2014 en Wayback Machine , Capítulo IV: Conjuntos reconocibles y racionales

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