Linguagens formais e Autômatos – 3

Para ver a segunda parte clique aqui

Expressões regulares – Toda Linguagem Regular pode ser descrita por uma expressão simples denominada Expressão Regular. Trata-se de um formalismo denotacional também considerado gerador, pois pode-se inferir como construir (“gerar”) as palavras de uma linguagem. É uma maneira de representar uma linguagem formada pela justaposição dos símbolos do alfabeto separados pelos símbolos de união ou concatenação.

Linguagem – Conjunto de palavras

L1 = {0,01,11} ou L2 = {111,000}

Operações

L1UL2 = {0,01,11,111,000}

L1L2 = {0111,0000,0011,…}

L1*={0000,010101,…)

Linguagens Regulares – São aquelas que podem ser representadas por expressão regular ou autômatos.

Exemplos:

• L=Cadeias que possuem apenas um 0 E={0,1}
  • 1*01*
• L=Cadeias que possuem todas as strings binárias E={0,1}
  • (0U1)*
• L=Cadeias que possuem todas as strings binárias exceto o vazio E={0,1}
  • (oU1)⁺
• L=Cadeias que começam com aa e terminam com bb E={a,b}
  • aa(aUb)*bb
• L=Cadeias que começam ou terminam com bb E={a,b}
  • bb(aUb)*U(aUb)*bb

Por definição, uma linguagem é Regular se, e somente se, é possivel construir um Autômato Finito (Determinístico, Não-Determinístico ou com Movimentos Vazios), que reconheça a linguagem.

Transformação de Autômato/ER

1. Incluir dois estados ( um inicial, que aponta para o inicial antigo por E(movimento vazio), e um estado final, todos os finais antigos do autômato deixam de ser finais e apontam por E para o novo).
2. Avaliar dois a dois os estados na tentativa de eliminar um terceiro.

Hierarquia de Chomsky

É a classificação de gramáticas formais descrita em 1959 pelo linguista Noam Chomsky. Esta classificação possui 4 níveis (Descritos na figura ao lado), sendo que os dois últimos níveis (os níveis 2 e 3) são amplamente utilizados na descrição de linguagem de programação e na implementação de interpretadores e compiladores. Mais especificamente, o nível 2 é utilizado em análise sintática (computação) e o nível 3 em análise léxica.

A classificação das gramáticas começa pelo tipo 0, com maior nível de liberdade em suas regras, e aumentam as restrições até o tipo 3. Cada nível é um super conjunto do próximo. Logo, uma gramática de tipo n é conseqüentemente uma linguagem de tipo n-1.

• Linguagem tipo 3: Regular
  • Reconhecida por um autômato finito
  • Representada por uma expressão regular
• Linguagem tipo 2: Livre de contexto
  • Reconhecida por um autômato de pilha
• Linguagem tipo 1: sensível ao contexto
• Linguagem tipo 0: Irrestrita
  • Máquina de Turing

Lema do Bombeamento

Diz que se pegarmos uma cadeia de tamanho maior do que a quantidade de estados do autômato, existe um pedaço dessa cadeia que pode ser bombeada (repetida em um looping) de forma que a cadeia gerada ainda pertence a linguagem.

Isso significa que existe um looping dentro do autômato. O lema do Bombeamento serve para provar que uma linguagem “NÃO” é regular. A demonstração de que uma linguagem é regular é feita através da criação de um autômato ou expressão regular.

Não é regular

-Afirme que é regular

-Escolha uma que você ache que não é regular

-Bombear

-Provar que não é regular.

O que foi descrito neste artigo é somente o começo dos estudos das linguagens formais. Foi dividido em 3 partes, é possível acessar a segunda parte clicando aqui, e a primeira parte clicando aqui. O artigo foi baseado no livro: Linguagens Formais e Autômatos, Série Livros Didáticos Segunda edição, de Paulo Fernando Blauth Menezes, com alguns pedaços de texto retirados da Wikipedia.