Cap 1 sipser

Disponível somente no TrabalhosFeitos
  • Páginas : 12 (2860 palavras )
  • Download(s) : 0
  • Publicado : 9 de maio de 2012
Ler documento completo
Amostra do texto
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ósusamos 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ômatofinito.

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 figurasseguintes, 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 naretaguarda 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 é mostradonas figuras seguintes, há quatro possíveis condições de entrada: "FRENTE" (significando que uma pessoa está em pé sobre o tapete em frente à porta), "RETAGUARDA" (significando que uma pessoa está em pé sobre o tapete na saída da porta), "AMBOS" (significando que pessoas estão sobre os dois tapetes), e "NENHUM" (significando que ninguém está sobre algum dos tapetes).
[pic]
Figura 1.2Diagrama que representa o controlador para uma porta automática.


[pic]
Figura 1.3
Tabela de transição para um controlador de uma porta automática.

O controlador move-se de estado para estado, dependendo da entrada que ele recebe. Quando está no estado FECHADO e recebe uma entrada NENHUM ou RETAGUARDA, ele permanece no estado FECHADO. Além disso, se a entrada AMBOS érecebida, ele permanece FECHADO, porque há o risco de derrubar alguém no tapete da retaguarda se a porta for aberta. Mas, se a entrada FRENTE for recebida, o controlador move-se para o estado ABERTO. No estado ABERTO, se a entrada FRENTE, RETAGUARDA, ou AMBOS é recebida, ele permanece em ABERTO. Se a entrada NENHUM é recebida, ele retorna para FECHADO.
Por exemplo, um controlador poderá começar noestado FECHADO e receber a seguinte série de sinais de entrada: FRENTE, RETAGUARDA, NENHUM, FRENTE, AMBOS, NENHUM, RETAGUARDA, NENHUM. Então, ele passaria pela série de estados: FECHADO (começando), ABERTO, ABERTO, FECHADO, ABERTO, ABERTO, FECHADO, FECHADO, FECHADO.
Analisando um controlador de uma porta automática como um autômato finito é útil, porque isto sugere formas padronizadas derepresentação como nas figuras 1.2 e 1.3. Esse controlador é um computador que possui apenas um bit de memória, capaz de memorizar em qual dos dois estados o controlador está. Outros dispositivos comuns possuem controladores com memórias um tanto maiores. Num controlador de elevador, um estado poderá representar o andar onde ele está e as entradas poderiam ser os sinais recebidos dos botões. Esse...
tracking img