Definiçoes linguagens formais

1. Conceitos Basicos sobre Linguagens e Operacoes com Linguagens

As Linguagens(linguagens formais) foram criadas para aproximar a linguagem humana das linguagens de programação. Estas procuram eliminar toda ambiguidade possível para que palavras reservadas tenham sempre o mesmo significado, podendo aparecer em qualquer parte no programa. Linguagens finitas podem ser representadas enumerando as cadeias(palavras) que fazem parte delas. Linguagens finitas ou com numero infinito de cadeias podem ser representadas atraves da gramatica, onde são descritas as regras que especificam a formação das cadeias. Sendo assim uma maquina que possui o conjunto dessas regras aceitarao ou não as cadeias. Operaçoes sobre linguagens regulares por exemplo, podem ser usadas para construir novas linguagens regulares a partir de linguagens regulares conhecidas, construir algoritmos ou provar propriedades. Linguagens regulares são fechadas(o resultado de operaçoes entre linguagens regulares é regular também) para varias operações, como a união, concatenação, complemento e intersecção. A linguagem vazia e linguagem conjunto vazio são linguagens regulares tambem.

2. Automatos Finitos Deterministicos e Expressoes Regulares e sua equivalencia

Um autômato finito tem um conjunto de estados, alguns dos quais são denominados estados finais. Quando os caracteres são lidos,são seguidos o conjunto de regras de transição e a maquina passa ou não de um estado para outro. Se após o último carácter o autômato encontra-se em um dos estados finais, a palavra foi reconhecida (ou seja, pertence à linguagem). Autômatos finitos são determinísticos, quando para cada combinação de estado e entrada existe uma única transição. AFDs e expressões regulares são equivalentes, pois descrevm exatamente a classe de linguagens regulares. Assim, é possível obter a expressão regular a partir do AFD, para isso convertemos o automato para um automato finito não deterministico generalizado e em seguida