Tribo do C.I.

Só mais um blog de informática (só que não)

Linguagens formais e Autômatos – 3

dezembro 1st, 2010

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.


Expressões Regulares e suas respectivas linguagens

Expressão Regular

Linguagem Representada

aa

Somente a palavra aa

ba*

Todas as palavras que iniciam por b, seguido por zero ou mais a

(a+b)*

Todas as palavras sobre {a,b}

(a+b)*aa(a+b)*

Todas as palavras contendo aa como subpalavra

a*ba*ba*

Todas as palavras contend exatamente dois b

(a+b)*(aa+bb)

Todas as palavras que terminam com aa ou bb

(a+E)(b+ba)*

Todas as palavras que não possuem dois a consecutivos.

Sobre Sheldon Led:
Desenvolvedor e palestrante desde 2009. Já trabalhou com sistemas legados e software de gestão, mas hoje atua somente com web. Já participou do desenvolvimento de alguns portais governamentais e sites utilizando a plataforma Joomla e WordPress. Apesar de ser um desenvolvedor full-stack, tem focado seus estudos em tecnologias front-end e busca apoiar e colaborar em projetos envolvendo Software Livre, seja em eventos, material para estudo ou contribuição de código.