Linguagem regular - Regular language

Na ciência da computação teórica e na teoria da linguagem formal , uma linguagem regular (também chamada de linguagem racional ) é uma linguagem formal que pode ser definida por uma expressão regular , no sentido estrito da ciência da computação teórica (em oposição a muitos motores de expressões regulares modernos, que são aumentados com recursos que permitem o reconhecimento de idiomas não regulares).

Alternativamente, uma linguagem regular pode ser definida como uma linguagem reconhecida por um autômato finito . A equivalência de expressões regulares e autômatos finitos é conhecida como teorema de Kleene (em homenagem ao matemático americano Stephen Cole Kleene ). Na hierarquia de Chomsky , as linguagens regulares são as linguagens geradas por gramáticas Tipo-3 .

Definição formal

A coleção de línguas regulares sobre um alfabeto Σ é definida recursivamente da seguinte forma:

• O idioma vazio Ø é um idioma regular.
• Para cada a ∈ Σ ( a pertence a Σ), a linguagem singleton { a } é uma linguagem regular.
• Se A é uma linguagem regular, A * ( estrela de Kleene ) é uma linguagem regular. Devido a isso, a linguagem de string vazia {ε} também é regular.
• Se A e B são linguagens regulares, então A ∪ B (união) e A • B (concatenação) são linguagens regulares.
• Nenhum outro idioma acima de Σ é regular.

Consulte expressão regular para sintaxe e semântica de expressões regulares.

Exemplos

Todas as linguagens finitas são regulares; em particular, a linguagem de string vazia {ε} = Ø * é regular. Outros exemplos típicos incluem o idioma que consiste de todas as cadeias sobre o alfabeto { um , b }, que contém um número par de um s, ou a língua que consiste de todas as cordas da forma: vários um s seguido por vários b s.

Um exemplo simples de uma linguagem que não é regular é o conjunto de strings { a ⁿ b ⁿ | n ≥ 0}. Intuitivamente, ele não pode ser reconhecido com um autômato finito, uma vez que um autômato finito tem memória finita e não consegue lembrar o número exato de a's. As técnicas para provar esse fato rigorosamente são fornecidas a seguir .

Formalismos equivalentes

Uma linguagem regular satisfaz as seguintes propriedades equivalentes:

1. é a linguagem de uma expressão regular (pela definição acima)
2. é a linguagem aceita por um autômato finito não determinístico (NFA)
3. é a linguagem aceita por um autômato finito determinístico (DFA)
4. pode ser gerado por uma gramática regular
5. é a linguagem aceita por um autômato finito alternado
6. é a linguagem aceita por um autômato finito bidirecional
7. pode ser gerado por uma gramática de prefixo
8. pode ser aceito por uma máquina de Turing somente leitura
9. pode ser definido na lógica monádica de segunda ordem ( teorema de Büchi-Elgot-Trakhtenbrot )
10. é reconhecido por algum monóide sintático finito M , o que significa que é a pré - imagem { w ∈ Σ ^* | f ( w ) ∈ S } de um subconjunto S de um monóide finito M sob um homomorfismo monóide f : Σ ^* → M do monóide livre em seu alfabeto
11. o número de classes de equivalência de sua congruência sintática é finito. (Este número é igual ao número de estados do autômato finito determinístico mínimo que aceita L. )

As propriedades 10. e 11. são abordagens puramente algébricas para definir linguagens regulares; um conjunto semelhante de afirmações pode ser formulado para um monóide M ⊆ Σ ^* . Nesse caso, a equivalência sobre M leva ao conceito de uma linguagem reconhecível.

Alguns autores usam uma das propriedades acima diferente de "1". como uma definição alternativa de línguas regulares.

Algumas das equivalências acima, particularmente aquelas entre os primeiros quatro formalismos, são chamadas de teorema de Kleene nos livros didáticos. Exatamente qual (ou qual subconjunto) é chamado de tal varia entre os autores. Um livro-texto chama a equivalência de expressões regulares e NFAs ("1" e "2" acima) de "teorema de Kleene". Outro livro-texto chama a equivalência de expressões regulares e DFAs ("1" e "3" acima) de "teorema de Kleene". Dois outros livros didáticos provam primeiro a equivalência expressiva de NFAs e DFAs ("2" e "3") e, em seguida, declaram o "teorema de Kleene" como a equivalência entre expressões regulares e autômatos finitos (o último diz que descreve "linguagens reconhecíveis") . Um texto orientado linguisticamente primeiro iguala gramáticas regulares ("4" acima) com DFAs e NFAs, chama as linguagens geradas por (qualquer uma) dessas "regulares", após o que introduz expressões regulares que designa para descrever "linguagens racionais", e finalmente afirma o "teorema de Kleene" como a coincidência de linguagens regulares e racionais. Outros autores simplesmente definem "expressão racional" e "expressões regulares" como sinônimos e fazem o mesmo com "linguagens racionais" e "linguagens regulares".

Aparentemente, o termo "regular" se origina de um relatório técnico de 1951, onde Kleene introduziu "eventos regulares" e acolheu explicitamente "quaisquer sugestões quanto a um termo mais descritivo" . Noam Chomsky , em seu artigo seminal de 1959, usou o termo "regular" em um significado diferente no início (referindo-se ao que é chamado de " forma normal de Chomsky " hoje), mas notou que suas "linguagens de estado finito" eram equivalentes às "linguagens regulares de Kleene eventos " .

Propriedades de fechamento

As linguagens regulares são fechadas sob várias operações, ou seja, se as linguagens K e L são regulares, então é o resultado das seguintes operações:

• as operações booleanas set-teórica : união K ∪ L , interseção K ∩ L , e complemento L , portanto, também em relação complemento K - L .
• as operações regulares: K ∪ L , concatenação e estrela de Kleene L ^* .${\ displaystyle K \ circ L}$
• as operações do trio : homomorfismo de string, homomorfismo de string inversa e interseção com linguagens regulares. Como consequência, eles são fechados sob transduções de estado finito arbitrárias , como o quociente K / L com uma linguagem regular. Ainda mais, linguagens regulares são fechados sob quocientes com arbitrárias línguas: Se L é regular, então L / K é regular para qualquer K .
• o reverso (ou imagem invertida) G ^R . Dado um autômato finito não determinístico para reconhecer L , um autômato para L ^R pode ser obtido invertendo todas as transições e trocando os estados inicial e final. Isso pode resultar em vários estados iniciais; As transições ε podem ser usadas para uni-los.

Propriedades de capacidade de decisão

Dados dois autômatos finitos determinísticos A e B , é decidível se eles aceitam a mesma linguagem. Como consequência, usando as propriedades de fechamento acima , os seguintes problemas também são decidíveis para autômatos finitos determinísticos A e B dados arbitrariamente , com as linguagens L _A e L _B aceitas , respectivamente:

• Contenção: L _A ⊆ L _B  ?
• Desarticulação: L _A ∩ L _B = {}?
• Vazio: é L _A = {}?
• Universalidade: L _A = Σ ^*  ?
• Membro: dado um ∈ Σ ^* , é um ∈ L _B  ?

Para expressões regulares, o problema de universalidade já é NP-completo para um alfabeto singleton. Para alfabetos maiores, esse problema é PSPACE completo . Se as expressões regulares forem estendidas para permitir também um operador de quadratura , com " A ² " denotando o mesmo que " AA ", ainda assim apenas as linguagens regulares podem ser descritas, mas o problema de universalidade tem um limite inferior de espaço exponencial e é de fato completo para espaço exponencial em relação à redução em tempo polinomial.

Resultados de complexidade

Na teoria da complexidade computacional , a classe de complexidade de todas as linguagens regulares é algumas vezes referida como REGULAR ou REG e é igual a DSPACE (O (1)), os problemas de decisão que podem ser resolvidos em espaço constante (o espaço usado é independente do tamanho de entrada ) REGULAR ≠ AC ⁰ , pois contém (trivialmente) o problema de paridade de determinar se o número de 1 bits na entrada é par ou ímpar e este problema não está em AC ⁰ . Por outro lado, REGULAR não contém AC ⁰ , porque a linguagem não regular dos palíndromos , ou a linguagem não regular, podem ser reconhecidas na AC ⁰ . ${\ displaystyle \ {0 ^ {n} 1 ^ {n}: n \ in \ mathbb {N} \}}$

Se uma linguagem não for regular, ela requer uma máquina com pelo menos Ω (log log n ) de espaço para reconhecer (onde n é o tamanho da entrada). Em outras palavras, DSPACE ( o (log log n )) é igual à classe das linguagens regulares. Na prática, a maioria dos problemas não regulares é resolvida por máquinas que ocupam pelo menos espaço logarítmico .

Localização na hierarquia de Chomsky

Linguagem regular em classes de hierarquia de Chomsky.

Para localizar as linguagens regulares na hierarquia de Chomsky , nota-se que toda linguagem regular é livre de contexto . O inverso não é verdadeiro: por exemplo, a linguagem que consiste em todas as cadeias de caracteres com o mesmo número de a 's que b ' s não tem contexto, mas não é regular. Para provar que uma linguagem não é regular, costuma-se usar o teorema de Myhill-Nerode e o lema do bombeamento . Outras abordagens incluem o uso de propriedades de fechamento de linguagens regulares ou quantificação da complexidade de Kolmogorov .

Subclasses importantes de linguagens regulares incluem

• Línguas finitas, aquelas que contêm apenas um número finito de palavras. Essas são linguagens regulares, pois é possível criar uma expressão regular que é a união de todas as palavras da linguagem.
• Linguagens livres de estrelas , aquelas que podem ser descritas por uma expressão regular construída a partir do símbolo vazio, letras, concatenação e todos os operadores booleanos (ver álgebra de conjuntos ) incluindo complementação, mas não a estrela de Kleene : esta classe inclui todas as linguagens finitas.

O número de palavras em um idioma normal

Deixe denotar o número de palavras de comprimento em . A função geradora comum para L é a série de potências formal${\ displaystyle s_ {L} (n)}$${\ displaystyle n}$${\ displaystyle L}$

${\ displaystyle S_ {L} (z) = \ sum _ {n \ geq 0} s_ {L} (n) z ^ {n} \.}$

A função geradora de uma linguagem L é uma função racional se L for regular. Portanto, para cada linguagem regular, a sequência é recursiva constante ; isto é, existe uma constante inteira , constantes complexas e polinômios complexos tais que para cada o número de palavras de comprimento em é . ${\ displaystyle L}$${\ displaystyle s_ {L} (n) _ {n \ geq 0}}$${\ displaystyle n_ {0}}$${\ displaystyle \ lambda _ {1}, \, \ ldots, \, \ lambda _ {k}}$${\ displaystyle p_ {1} (x), \, \ ldots, \, p_ {k} (x)}$${\ displaystyle n \ geq n_ {0}}$${\ displaystyle s_ {L} (n)}$${\ displaystyle n}$${\ displaystyle L}$${\ displaystyle s_ {L} (n) = p_ {1} (n) \ lambda _ {1} ^ {n} + \ dotsb + p_ {k} (n) \ lambda _ {k} ^ {n}}$

Assim, a não regularidade de certas línguas pode ser provada contando as palavras de um determinado comprimento em . Considere, por exemplo, a linguagem Dyck de strings de parênteses equilibrados. O número de palavras de comprimento na língua dyck é igual ao número catalão , que não é da forma , testemunhando a não regularidade da língua dyck. Deve-se ter cuidado, pois alguns dos autovalores podem ter a mesma magnitude. Por exemplo, o número de palavras de comprimento na linguagem de todas as palavras binárias pares não é da forma , mas o número de palavras de comprimento par ou ímpar é desta forma; os autovalores correspondentes são . Em geral, para cada linguagem regular existe uma constante tal que, para todas , o número de palavras de comprimento é assintoticamente . ${\ displaystyle L '}$${\ displaystyle L '}$${\ displaystyle 2n}$ ${\ displaystyle C_ {n} \ sim {\ frac {4 ^ {n}} {n ^ {3/2} {\ sqrt {\ pi}}}}}$${\ displaystyle p (n) \ lambda ^ {n}}$${\ displaystyle \ lambda _ {i}}$${\ displaystyle n}$${\ displaystyle p (n) \ lambda ^ {n}}$${\ displaystyle 2, -2}$${\ displaystyle d}$${\ displaystyle a}$${\ displaystyle dm + a}$${\ displaystyle C_ {a} m ^ {p_ {a}} \ lambda _ {a} ^ {m}}$

A função zeta de uma linguagem L é

${\ displaystyle \ zeta _ {L} (z) = \ exp \ left ({\ sum _ {n \ geq 0} s_ {L} (n) {\ frac {z ^ {n}} {n}}} \direito)\ .}$

A função zeta de uma linguagem regular não é em geral racional, mas a de uma linguagem cíclica arbitrária é.

Generalizações

A noção de uma linguagem regular foi generalizada para palavras infinitas (ver ω-autômato ) e para árvores (ver autômato de árvore ).

Conjunto racional generaliza a noção (de linguagem regular / racional) para monóides que não são necessariamente livres . Da mesma forma, a noção de uma linguagem reconhecível (por um autômato finito) tem homônimo como conjunto reconhecível sobre um monóide que não é necessariamente livre. Howard Straubing observa em relação a esses fatos que “O termo" linguagem regular "é um pouco infeliz. Artigos influenciados pela monografia de Eilenberg freqüentemente usam o termo "linguagem reconhecível", que se refere ao comportamento de autômatos, ou "linguagem racional", que se refere a analogias importantes entre expressões regulares e séries de potências racionais. (Na verdade, Eilenberg define subconjuntos racionais e reconhecíveis de monóides arbitrários; as duas noções não coincidem, em geral.) Esta terminologia, embora mais motivada, nunca realmente pegou, e a "linguagem regular" é usada quase universalmente. ”

A série racional é outra generalização, desta vez no contexto de uma série de poder formal sobre uma semifiação . Esta abordagem dá origem a expressões racionais ponderadas e autômatos ponderados . Nesse contexto algébrico, as linguagens regulares (correspondendo a expressões racionais ponderadas por Boolean ) são geralmente chamadas de linguagens racionais . Também neste contexto, o teorema de Kleene encontra uma generalização chamada teorema de Kleene-Schützenberger .

Aprendendo com exemplos

Notas

Referências

Leitura adicional

• Kleene, SC : Representação de eventos em redes nervosas e autômatos finitos. Em: Shannon, CE, McCarthy, J. (eds.) Automata Studies, pp. 3-41. Princeton University Press, Princeton (1956); é uma versão ligeiramente modificada de seu relatório de 1951 da RAND Corporation com o mesmo título, RM704 .
• Sakarovitch, J (1987). "Teorema de Kleene revisitado". Tendências, técnicas e problemas em ciência da computação teórica . Notas de aula em Ciência da Computação. 1987 . pp. 39–50. doi : 10.1007 / 3540185356_29 . ISBN 978-3-540-18535-2.

links externos

• Mídia relacionada à linguagem regular no Wikimedia Commons
• Zoo de Complexidade : Classe REG