Linguagem regular

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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. Note que os recursos das "expressões regulares" fornecidas com várias linguagens de programação são aumentada com características que as tornam capazes de reconhecer linguagens que não podem ser expressas por expressões regulares formais (como formalmente é definido abaixo).

Na hierarquia de chomsky, linguagens regulares são definidas para ser linguagens que são geradas por gramáticas tipo 3 (gramática regulares). Linguagens regulares são muito úteis na análise de entradas e no projeto de uma linguagem de programação.


Definição Formal[editar | editar código-fonte]

A coleção de linguagens regulares sobre um alfabeto Σ é definida recursivamente seguindo as regras abaixo:

  • A linguagem vazia Ø é uma linguagem regular.
  • A linguagem cadeia vazia {ε} é uma linguagem regular.
  • Para cada a ∈ Σ (a pertence a Σ), a linguagem do conjunto unitário {a} é uma linguagem regular.
  • Se A e B são linguagens regulares, então AB (união), AB (concatenação), e A* (Fecho de Kleene ou estrela) são linguagens regulares.
  • Nenhuma outra linguagem sobre Σ é regular.

Veja Expressão regular para ver a semântica e a síntaxe dessas operações. Note que os casos acima são consequências das regras da definição das expressões regulares.

Exemplos

Toda linguagem finita é regular. Outros exemplos típicos incluem a linguagem consistindo de todas as cadeias sobre o alfabeto {a,b} que contenham um número par de as, ou a linguagem consistindo de todas as cadeias da forma: vários as seguido por vários bs.

Um simples exemplo de linguagem que não é regular é o conjunto de cadeias \{a^nb^n\,\vert\; n\ge 0\}. Isso porque nessa linguagem, o número de as controla o número de bs, que não são permitidos por qualquer uma das regras acima. Ver mais em 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:

As propriedades acima são usadas, ocasionalmente, como um definição alternativa das linguagens regulares.


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). REGULARAC0, 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 \{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.


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:

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 é \{ 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 : uwL se e somente se vwL 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 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 L existe constantes \lambda_1,\,\ldots,\,\lambda_k e polinômios p_1(x),\,\ldots,\,p_k(x) tal que para cada n o número s_L(n) de palavras de tamanho n em L satisfaz a equação s_L(n)=p_1(n)\lambda_1^n+\dotsb+p_k(n)\lambda_k^n. Assim, a não regularidade de algumas linguagens L' podem ser provadas pela enumeração das palavras em L'. Considere, por exemplo, a Linguagem de Dyck de cadeias de parênteses balanceados. O número de palavras de tamanho 2n na linguagem Dyck é igual ao número Catalão C_n\sim\frac{4^n}{n^{3/2}\sqrt{\pi}},o qual não é da forma 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 xL tal que |x| ≥ n, x pode ser reescrito da forma wyz, |y| ≤ n, e ∀ i, i ≥ 0 xy^{i}zL

Veja também[editar | editar código-fonte]


Referências[editar | editar código-fonte]

Ambox rewrite.svg
Esta página precisa ser reciclada de acordo com o livro de estilo.
Sinta-se livre para editá-la para que esta possa atingir um nível de qualidade superior.
Editor: considere colocar o mês e o ano da marcação. Isso pode ser feito automaticamente, substituindo esta predefinição por {{subst:rec}}
  1. M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomial-time hierarchy. Math. Systems Theory, 17:13–27, 1984.
  2. Cook, Stephen; Nguyen, Phuong. In: Stephen. Logical foundations of proof complexity. 1. publ. ed. Ithaca, NY: Association for Symbolic Logic, 2010. 75 p. ISBN 052151729X
  3. J. Hartmanis, P. L. Lewis II, and R. E. Stearns. Hierarchies of memory-limited computations. Proceedings of the 6th Annual IEEE Symposium on Switching Circuit Theory and Logic Design, pp. 179–190. 1965.


Teoria de autômatos: linguagem formal e gramática formal
Hierarquia
Chomsky
Gramática Linguagem Reconhecedor
Tipo-0 Irrestrita Recursivamente enumerável Máquina de Turing
-- -- Recursiva Máquina de Turing que sempre para
Tipo-1 Sensível ao contexto Sensível ao contexto Autômato linearmente limitado
Tipo-2 Livre de contexto Livre de contexto Autômato com pilha
Tipo-3 Regular Regular Autômato finito