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.
| Teoria de Autômatos: Linguagem formal e gramática formal | |||
|---|---|---|---|
| Hierarquia Chomsky |
Gramática | Linguagem | Reconhecedor |
| Tipo-0 | Estrutura de frase | Recursivamente enumerável | Máquina de Turing |
| -- | Estrutura de frase | Recursiva | Máquina de Turing |
| Tipo-1 | Sensíveis ao contexto | Sensíveis ao contexto | Máquina de Turing com memória limitada |
| Tipo-2 | Livre de contexto | Livre de contexto | Autômato com pilha |
| Tipo-3 | Regular | Regular | Autômato finito |
