Linguagem regular

Origem: Wikipédia, a enciclopédia livre.

Uma linguagem regular é uma linguagem formal (ou seja, um possível conjunto finito ou infinito de sequências de símbolos de um determinado alfabeto) que satisfaz as seguintes propriedades equivalentes:

• Pode ser aceite por : uma máquina de estados finitos determinística, uma máquina de estados finitos não determinística ou uma autômato finito alternado;
• Pode ser aceite por : uma máquina de Turing somente de leitura;
• Pode ser descrita por : uma expressão regular;
• Poder ser gerada por : uma gramática regular ou por uma gramática de prefixo;
• Pode ser definida na lógica de segunda ordem monádica;

Desse resumo entende-se que uma linguagem regular pode ser especificada por uma gramática regular que a gera, ou por uma expressão regular que a denote, ou ainda por um autômato finito que reconhece suas sentenças.

[editar] Liguagens regulares sobre um alfabeto

A coleção de linguagens regulares sobre um alfabeto Σ é definida recursivamente como:

• A linguagem vazia Ø é uma linguagem regular.
• A linguagem da string vazia { ε } é uma linguagem regular.
• Para cada a ∈ Σ, a linguagem Singleton { a } é uma linguagem regular.
• Se A e B são linguagens regulares, então A U B, A • B, e A*.
• Nenhumas outras linguagens regulares sobre Σ são regulares.

Todas linguagens finitas são regulares. Outros exemplos típicos incluem a linguagem que consiste em todas as strings sobre o alfabeto {a, b} que contem um mesmo número de as ou a liguagem que consiste de todas as strings sob a forma diversos as seguidos por diversos

[editar] Propriedades de Fechamento

Os resultados das operações de união, intersecção e conjunto diferença, quando aplicados a linguagens regulares eles próprios são uma linguagem regular, o complemento de toda linguagem regular sobre o seu alfabeto é uma linguagem regular também. A inversão de qualquer string de uma linguagem regular gera outra linguagem regular. A concatenação de duas linguagens regulares (no sentido de concatenar cada string da primeira linguagem com cada string da segunda) também gera uma linguagem regular. A operação de embaralhamento (shuffle), quando aplicada a duas linguagens regulares, gera outra linguagem regular.

Não tente entender, isso não serve pra nada...

[editar] Decidindo se uma linguagem é ou não regular

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 as e de bs é livre de contexto mas não é regular. Toda linguagem regular surge dessa forma.

Se L é um subconjunto de Σ*, define-se a seguinte relação de equivalência de ~ 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; 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.