Analise e complexidade de algoritmos

[LINGUAGENS FORMAIS E AUTÔMATOS]

Entendento a importância da matéria Linguagens Formais e Autômatos dentro do curso de Ciências da Computação. Buscando um conhecimento básico de Lógica Booleana e as definições para termos como “Palavras”, “Alfabeto” e “Gramática” dentro desse universo.

1. INTRODUÇÃO
A importância da Teoria das Linguagens Formais e dos Autômatos (LFA) está no estudo de modelos matemáticos que possibilitam a especificação e o reconhecimento de linguagens (no sentido amplo da palavra), suas classificações, estruturas, propriedades, características e inter-relacionamentos.
Essa teoria é de suma importância na Ciência da Computação pois ela ela tanto apoia outros aspectos teóricos da Ciência da Computação (decidibilidade, computabilidade, complexidade computacional, por exemplo), como fundamenta diversas aplicações computacionais tais como processamento de linguagens, reconhecimento de padrões, modelagem de sistemas.
2. LÓGICA BOOLEANA (CONCEITOS BÁSICOS)
Álgebra de Booleana é utilizada para exprimir os resultados ou saídas de circuitos lógicos e para manipular variáveis lógicas, com a finalidade de se obter o melhor circuito para uma determinada função lógica. Chamamos de variável Booleana a uma variável que pode assumir só duas condições (dois valores).
Um exemplo de variável Booleana é uma chave, que só pode estar aberta ou fechada, não existe outra condição. Outro exemplo é uma lâmpada, que só pode estar acesa ou apagada. Em eletrônica digital costumamos associar a uma variável Booleana os símbolos “0“ e “1“ aos estados que a variável pode assumir. Desta forma lâmpada acesa poderia ser “1“ e conseqüentemente apagada “0“, mas poderia ser o contrário depende da convenção adotada.

Níveis Lógicos
0 (zero) 1 (um)
Falso Verdadeiro
Desligado Ligado
Baixo Alto
Não Sim
Chave aberta Chave fechada
Apagado Acesso

Operações em Álgebra Booleana
Adição Lógica = +, OU, OR
Multiplicação Lógica = ., E, AND
Complementação Lógica/Inversão =