Introdução às Linguagens Formais e Autômatos/Linguagens Regulares

Linguagem regular Origem: Wikipédia, a enciclopédia livre. (Redirecionado de Linguagens Regulares) Na teoria da ciência da computação e teoria formal de linguagem, uma linguagem regular é uma linguagem formal que pode ser expressa usando expressões regulares, ou seja, uma linguagem produzida utilizando as operações de concatenação, união e fecho de Kleene sobre os elementos de um alfabeto. De acordo com a hierarquia de Chomsky, linguagens regulares são aquelas geradas por gramática regulares.

As linguagens regulares são utilizadas para descrever dispositivos que realizam computações simples, como os autômatos finitos, pois representam a linguagem mais elementar classificada pela hierarquia de Chomsky que não requer memória para ser reconhecida.

No projeto de linguagens de programação, as linguagens regulares são úteis no processo de análise sintática.

Índice [esconder] 1 Definição formal 1.1 Exemplos 2 Equivalência com outros formalismos 3 Resultados sobre a Complexidade 4 Propriedade do Bombeamento 5 Propriedades de Fechamento 6 Propriedade de Decisão 7 Decidindo se uma linguagem é regular 8 Linguagens Finitas 9 O número de palavras de uma linguagem regular 9.1 Teorema da iteração para linguagens regulares 10 Ver também 11 Referências Definição formal[editar | editar código-fonte] A coleção de linguagens regulares sobre um alfabeto Σ qualquer é definida recursivamente seguindo as regras abaixo:

A linguagem vazia (L = Ø) é uma linguagem regular. Se x é um elemento qualquer do alfabeto Σ, a linguagem formado pelo conjunto desse elemento (L = {x}) é uma linguagem regular. Se A e B são linguagens regulares, então as linguagens formadas pela união (L = A ∪ B), concatenação (L = A • B) e fecho de Kleene (L = A* ou L = B*) desses conjuntos também são linguagens regulares. Nenhuma outra linguagem sobre o alfabeto Σ é regular. Veja Expressão regular para ver a semântica e a sintaxe dessas operações. Note que os casos acima são consequências das regras da definição das expressões regulares.

Exemplos[editar | editar código-fonte] Todas as linguagens finitas são regulares, em particular a linguagem composta unicamente pela cadeia vazia (L = {ε} = Ø*) é regular. Considerando o alfabeto Σ = {a, b}, é possível descrever linguagens regulares como "todas cadeias que contenham um número par de 'a'" ou "todas cadeias formadas por uma quantidade qualquer de 'a' seguido de uma quantidade qualquer de 'b'" e assim por diante.

O que não pode ser considerado uma linguagem regular são as linguagens que requerem a atuação de uma memória para estruturar os elementos de suas cadeias, isto é, quando a frequência de um elemento da cadeia determina a frequência de outro elemento da mesma cadeia. Portanto, linguagens como "todas cadeias de 'a' seguido de 'b', onde o número de 'a' é igual ao de 'b'", não são regulares pois o número de 'a' determina o número de 'b'.

Existem inúmeras técnicas para determinar se uma linguagem é regular ou não, sendo comum a utilização do lema do bombeamento para linguagens regulares.

Equivalência com outros formalismos[editar | editar código-fonte] Uma linguagem regular satisfaz as seguintes propriedades que são equivalentes:

ela é a linguagem descrita por uma expressão regular. ela pode ser aceita por um autômato finito determinístico. ela pode ser aceita por um autômato finito não determinístico. ela pode ser aceita por um autômato finito alternado. ela pode ser gerada por uma gramática regular. ela pode ser gerada por uma gramática de prefixos. ela pode ser aceita por uma Máquina de Turing que apenas faz leituras. ela pode ser definida em um monádico da lógica de segunda ordem. ela é reconhecida por algum Monoide finito. Alguns autores utilizam a equivalência de linguagens regulares com outros formalismos como definição alternativa para as mesmas.

Resultados sobre a Complexidade[editar | editar código-fonte] Na teoria da complexidade computacional, a classe de complexidade de todas linguagens regulares são ocasionalmente chamadas como REGULAR ou REG e equivale a DSPACE(O(1)), o problema de decisão pode ser resolvido em um espaço constante (o espaço usado é independente do tamanho da entrada). REGULAR ≠ AC0, uma vez que REG (trivialmente) contém o problema da paridade de determinar se o número de bits 1 na entrada é par ou ímpar e este problema não está naAC0.[1] Em contrapartida, REGULAR não contém AC0, porque as linguagens não regular dos palíndromos, ou a linguagen não regular {\displaystyle \{0^{n}1^{n}:n\in \mathbb {N} \}} {\displaystyle \{0^{n}1^{n}:n\in \mathbb {N} \}}, ambas, podem ser reconhecidas em AC0.[2]

Se uma linguagem é não regular, ela requer uma máquina que no mínimo Ω(log log n) de espaço para reconhecê-la (onde n é o tamaho da entrada).[3] Em outras palavras, DSPACE(O(log log n)) é equivalente a classe das linguagens regulares. Na prática, grande parte das linguagens não regulares são resolvidas por máquinas que tenha no mínimo espaço logarítmico.

Propriedade do Bombeamento[editar | editar código-fonte] Lema do bombeamento

Propriedades de Fechamento[editar | editar código-fonte] As linguagens regulares são fechadas sobre várias operações, ou seja, se uma linguagem K e L são regulares, então o resultado das seguintes operações também é regular:

as operações teóricas de conjunto  : união {\displaystyle K\cup L} {\displaystyle K\cup L}, interseção {\displaystyle K\cap L} {\displaystyle K\cap L}, e complemento {\displaystyle {\bar {L}}} {\displaystyle {\bar {L}}}. Consequentemente, diferença {\displaystyle K-L} {\displaystyle K-L} também é válida, já que é composta pela interseção e pelo complemento. as operações regulares: união {\displaystyle K\cup L} {\displaystyle K\cup L}, concatenação {\displaystyle K\circ L} {\displaystyle K\circ L} e estrela {\displaystyle L^{*}} {\displaystyle L^{*}}. as operações da família de linguagens abstratas: cadeia homomórfica, cadeia invesa homomórfica, e interseção com linguagens regulares. Como conseqüência, elas são fechadas sob arbitrária estados finitos transduções, como quociente {\displaystyle K/L} {\displaystyle K/L} com uma linguagem regular. Além disso, as linguagens regulares são fechadas sob quocientes com línguas arbitrárias: Se L é regular, então L / K é regular para qualquer K. o reverso (ou imagem espelhada) {\displaystyle L^{R}} {\displaystyle L^{R}}. Propriedade de Decisão[editar | editar código-fonte] Problema de decisão

Decidindo se uma linguagem é regular[editar | editar código-fonte]

Hierarquia de Chomsky Ao localizar as linguagens regulares na hierarquia de Chomsky, observe que todas as linguagens regulares são livres de contexto. O contrário já não é verdadeiro: por exemplo, uma linguagem que consiste de todas as strings tendo o mesmo número de a's e de b's é livre de contexto mas não é regular. Para provar que uma linguagem como essa não é regular, usamos o Teorema de Myhill-Nerode ou o lema do bombeamento.

Existe duas aproximações puramente algébricas que definem uma linguagem regular. Se:

Σ é um alfabeto finito, Σ* denota uma monoide livre sobre Σ que é composta por todas as cadeias formadas por Σ, f : Σ* → M é uma monoide homomórfica onde M é uma monoide finita, S é um subconjunto de M então o conjunto é {\displaystyle \{w\in \Sigma ^{*}\,|\,f(w)\in S\}} {\displaystyle \{w\in \Sigma ^{*}\,|\,f(w)\in S\}} é regular. Toda linguagem regular surge dessa forma.

Se L é um subconjunto de Σ*, define-se a seguinte relação de equivalência de ~ (conhecida como relação sintática) sobre Σ*: u ~ v é definida por : uw ∈ L se e somente se vw ∈ L para todo w ∈ Σ*.

A linguagem L é regular se e somente se o número de classes equivalentes de ~ é finita (Uma prova disso é fornecida no artigo da monoide sintática); se esse é o caso, esse número é igual ao número de estados de um autômato finito determinístico mínimo que aceita L.

Um conjunto similar de declarações pode ser formulado por uma monoide {\displaystyle M\subset \Sigma ^{*}} {\displaystyle M\subset \Sigma ^{*}}. Nesse caso, a equivalência sobre M leva ao conceito de uma linguagem reconhecível.

Linguagens Finitas[editar | editar código-fonte] Um subconjunto específico da classe das linguagens regulares é o conjunto das linguagens finitas - aqueles que contêm apenas um número finito de palavras. Essas linguagens são regulares, já que é possível criar uma expressão regular que é a união de cada palavra da linguagem.

O número de palavras de uma linguagem regular[editar | editar código-fonte] Para qualquer linguagem {\displaystyle L} L existe constantes {\displaystyle \lambda _{1},\,\ldots ,\,\lambda _{k}} {\displaystyle \lambda _{1},\,\ldots ,\,\lambda _{k}} e polinômios {\displaystyle p_{1}(x),\,\ldots ,\,p_{k}(x)} {\displaystyle p_{1}(x),\,\ldots ,\,p_{k}(x)} tal que para cada {\displaystyle n} n o número {\displaystyle s_{L}(n)} {\displaystyle s_{L}(n)} de palavras de tamanho {\displaystyle n} n em {\displaystyle L} L satisfaz a equação {\displaystyle s_{L}(n)=p_{1}(n)\lambda _{1}^{n}+\dotsb +p_{k}(n)\lambda _{k}^{n}} {\displaystyle s_{L}(n)=p_{1}(n)\lambda _{1}^{n}+\dotsb +p_{k}(n)\lambda _{k}^{n}}. Assim, a não regularidade de algumas linguagens {\displaystyle L'} {\displaystyle L'} podem ser provadas pela enumeração das palavras em {\displaystyle L'} {\displaystyle L'}. Considere, por exemplo, a Linguagem de Dyck de cadeias de parênteses balanceados. O número de palavras de tamanho {\displaystyle 2n} 2n na linguagem Dyck é igual ao número Catalão {\displaystyle C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}}} {\displaystyle C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}}},o qual não é da forma {\displaystyle p(n)\lambda ^{n}} {\displaystyle p(n)\lambda ^{n}}, comprovando a não regularidade da linguagem de Dyck.

Teorema da iteração para linguagens regulares[editar | editar código-fonte] Se L é uma linguagem regular, então existe um n tal que para todo x ∈ L tal que |x| ≥ n, x pode ser reescrito da forma wyz, |y| ≤ n, e ∀ i, i ≥ 0 {\displaystyle xy^{i}z} {\displaystyle xy^{i}z} ∈ L