Cap 1 sipser

Capítulo 01
Linguagens Regulares

A Teoria da Computação inicia com uma pergunta: O que é um computador ? Talvez seja uma pergunta tola, a partir do momento que minha filha de quatro anos sabe que esta coisa na qual eu teclo é um computador. Mas, esses computadores reais são um tanto complicados demais para que nos permitam fazer diretamente uma teoria matemática manuseável. Em vez disso, nós usamos um computador idealizado chamado de modelo computacional. Como em qualquer modelo na ciência, um modelo computacional poderá ser acurado em algumas maneiras, mas, talvez não seja em outras. Assim, nós utilizaremos diferentes modelos computacionais, dependendo do aspecto que nós queremos focalizar. Nós começaremos com o modelo mais simples, chamado de máquina de estado finito ou autômato finito.

1.1
Autômato Finito Autômatos finitos são bons modelos para computadores com uma quantidade de memória extremamente limitada. O que um computador pode fazer com uma memória tão pequena ? Muitas coisas úteis! Na verdade, nós interagimos com esses computadores todo o tempo, a partir do momento que eles fazem parte de vários dispositivos eletromecânicos. Como mostrado nas figuras seguintes, o controlador de uma porta automática é um exemplo de tal dispositivo. Constantemente encontradas nas entradas e saídas de supermercados, portas automáticas se abrem quando sentem que uma pessoa está se aproximando. Uma porta automática possui um tapete na frente para detectar a presença de uma pessoa que está na eminência de atravessar a porta. Um outro tapete está localizado na retaguarda da porta para que o controlador possa segurar a porta aberta o bastante para a pessoa passar, como também para que a porta quando abrir não bata em alguém que esteja em pé atrás dela.

[pic] Figura 1.1 Vista aérea de uma porta automática.

O controlador pode estar em dois estados: "ABERTO" ou "FECHADO", representando as condições correspondentes da porta. Como é mostrado