Lista de Exercício - Teoria da Computação

Prévia do material em texto

1) Explique o fundamento sobre o qual baseia-se a demonstração de equivalência entre AFNs e AFDs.
R: A premissa é que um autômato finito não-determinístico possui sempre um equivalente determinístico. 
Assim, partindo do estado inicial q0, faz se a leitura de uma entrada “a”, por exemplo, que direciona para dois estados diferentes não-finais q2 e q3, pode-se haver um estado equivalente chamado de q23 que possui a mesma função lógica na estrutura do autômato, ou seja, a sequência (próxima leitura) será direcionada para algum estado que será o mesmo (ou equivalente) aos direcionamentos a partir de q2 e q3.
Além dos direcionamentos seguintes serem logicamente equivalentes, é imprescindível que haja ao menos um estado final equivalente e que respeite as condições de aceita e rejeita do autômato finito não-determinístico.
As transições vazias também são consideradas no processo de criação do autômato, assim, a cada novo estado gerado deve-se aplicar a função fecho-vazio, afim de verificar se haverão novos estados criados.
2) Dado o alfabeto A = {x,w,y,z}, forneça os AFD’s M = (∑,Q,δ,q0, F) que aceitam as seguintes linguagens:
a) L1 = {w ∈ A* | w possui exatamente três x’s ou exatamente dois z’s}
R: O grafo que representa o autômato está representado pela figura 1, abaixo. A máquina, portanto, é escrita como:
M = ({x, z}, {q0, q1, q2, q3, q4, q5}, δ4, q0, {q3, q5})
Figura 1:
b) L3 = {w ∈ A* | w possui número par de x e número par de w}, considere que 0 é par.
R: O grafo que representa o autômato está representado pela figura 2, abaixo. A máquina, portanto, é escrita como:
M = ({x,w}, {q0, q1, q2} , δ2, q0, {q0})
Figura 2
3) Defina uma expressão regular que gere a mesma linguagem do exercício 2b).
R: RegEx: (xx)*(ww)* -> Esta expressão regular possui os asteriscos, pois o enunciado do exercício 2b) considera 0 como par, assim se houver a palavra vazia, a mesma será aceita pelo autômato.
4) Minimize o AFD M4 ({a,b,c}, {q0, q1, q2, q3, q4}, δ4, q0, {q3, q4})
R: 
Passo 1: Construção da tabela de equivalência de estados:
Passo 2: Marcar os estados que não podem possuir equivalência, por ser junção de estado final com não-final.
Passo 3: Analisar os estados não marcados, buscando verificar se há condições de aceita e rejeita equivalente, caso não haja, marca-se na tabela.
Estado {q0,q1}
Como ao ler a entrada “c” q1 direciona para o estado final q3 enquanto q0 ao ler “c” é quebrado, concluímos que {q0,q1} não é equivalente e marcamos na tabela. 
Estado {q0,q2}
Analogamente ao estado {q0,q1}, o estado {q0,q2} também apresenta a mesma divergência ao ler a entrada “c”, pois q4 é um estado final, logo {q0,q2} não é equivalente e deve ser marcado na tabela.
Estado {q1,q2}
Ao ler a entrada “a”, q2 fica em q2 mesmo, enquanto q1 se mantém em q1, nada nos dizendo sobre a equivalência, pois ambos são estados não-finais. Assim, devemos analisar a próxima entrada. Ao ler “b” ambos, q1 e q2 direcionam para o estado inicial q0 não-final, ainda não nos dizendo sobre a equivalência. Assim, analisamos a última entrada “c”. q1 direciona para o estado final q4 e q1 direciona para o estado final q3. 
Assim, podemos dizer que q1 e 2 são estados equivalentes, pois ao final das entradas ambos direcionaram para estados finais, ou seja, a mesma linguagem é aceita para ambos de maneira equivalente.
Estado {q3,q4}
Ambos q3 e q4 são estados finais, logo vamos analisar as entradas para dizer se são equivalentes.
Ao ler “a” q3 vai para q2 enquanto q4 vai para q1, como ambos estados são não-finais, nada nos diz por enquanto.
Ao ler “b” q3 vai para q4 e q4 para q3, como ambos são estados finais, podemos dizer que {q3,q4} são equivalentes
Assim, temos nossa tabela após todas as verificações e marcações:
Passo 4: Unificar os estados equivalente, criando o autômato minimizado.
{q1,q2} => Unificado em q12
{q3,q4} => Unificado em q34
Resultado final:
5) Use o Lema do Bombeamento para demonstrar que a linguagem abaixo não é regular. L4 = {an, bm, cn I m, n ≥ 0}
R: Para aplicar o Lema do Bombeamento, assumo que a L4 é uma linguagem regular, assim se a mesma não cumprir com os requisitos de uma, provamos por absurdo que ela não pode ser regular.
Portanto, para L4 ser regular, deve ser possível aplicar um Bombeamento de forma tal que o lado direito seja sempre maior ou igual ao lado esquerdo da linguagem s que aceita a mesma linguagem de L4.
Logo, podemos dizer que s é representada por: s = apbmcp, sendo ‘p’ o tamanho do bombeamento.
Assim, dividindo s em 3 partes (xyz), temos as possibilidades:
· y é composta por a’s
· y é composta por b’s
· y é composta por c’s
· y é composta por ab’s
· y é composta por bc’s
· y é composta por abc’s
Considerando p = 3, temos que: a3bmc3 = aaabmccc, logo como o tamanho de p = 3, apenas consideraremos a possibilidade em que y é composta por a’s, as demais já não são possíveis nesta demonstração.
Sabemos ainda, por meio do Lema do Bombeamento que |xy| ≤ p (tamanho de xy menor igual ao tamanho do bombeamento) para toda expressão regular.
Agora, considerando x = a, y = aa e z = bmccc, aplicamos o bombeamento, de forma que xyiz, (sendo i o número de ciclos do bombeamento) tenha à esquerda |xy| ≤ à direita |z|.
Então, fazendo i = 3, temos:
|xy3| = aaaaaaa
|z| = bmccc
Como pode-se ter ‘m’ arbitrário, se m < 4, |z| ≤ 6, assim |xy³| > |z| o que não é permitido para uma Linguagem Regular