AspectosTeoricos_Aula01

Prévia do material em texto

Aspectos Teóricos da Computação 
1º semestre 2019 1/7 
 
Curso: Ciência da Computação 
Disciplina: Aspectos Teóricos da Computação 
Profª Luciana Ap. Oliveira Betetto 
 
Aula 01 
1. Linguagens Formais 
Com a finalidade de estudar os princípios básicos do computador, constroem-se modelos de 
computadores abstratos para resolução dos problemas. 
Para modelar o hardware de um computador é introduzido o conceito de autômatos. Um 
autômato é uma construção que possui todas as características indispensáveis de um 
computador digital: entrada, saída, armazenagem temporária, tomadas de decisão. Um 
autômato é um reconhecedor de linguagem. Através dos reconhecedores é possível 
identificar se a cadeia de símbolos pertence ou não a uma linguagem. 
Existe uma hierarquia, chamada de Hierarquia de Chomsky (Figura 1), a qual é responsável 
pela classificação das classes de linguagens. Noah Chomsky definiu essas classes como 
potenciais modelos para as linguagens naturais: 
 
 
 
 
 
 
 
 
 
 
 
Figura 1. Hierarquia de Chomsky 
 
A tabela abaixo traz uma correspondência entre as classes de linguagens, gramáticas e 
reconhecedores. 
Linguagem Gramática Reconhecedor 
Tipo 0 – Enumeráveis Recursivamente Gram. Irrestritas Máquinas de Turing 
Tipo 1 – Sensíveis ao Contexto Gram. sensíveis ao contexto Autômato Limitado Linearmente 
Tipo 2 – Livres de Contexto Gram. Livres de Contexto Autômatos com Pilha 
Tipo 3 - Regulares Gram. Regulares Autômatos Finitos 
 
Linguagens Regulares 
 
 
3 
Linguagens Livres de Contexto 
 
 
 
 
2 
Linguagens Sensíveis ao Contexto 
 
 
 
 
 
 
 
1 
Linguagens Enumeráveis Recursivamente 
 
 
 
 
 
 
 
 
 
 
0 
Aspectos Teóricos da Computação 
1º semestre 2019 2/7 
2. Autômatos 
Um autômato é um modelo abstrato de um computador digital composto por um arquivo de 
entrada, arquivo de saída, memória e unidade de controle. 
O arquivo de entrada armazena uma cadeia sobre um alfabeto. O mecanismo de leitura lê 
a cadeia da esquerda para a direita, um símbolo por vez. 
O arquivo de saída armazena uma cadeia sobre um alfabeto produzido pelo autômato. 
Memória é um número finito de células que armazenam símbolos de um alfabeto. O 
autômato pode ler e alterar o conteúdo da memória. 
A unidade de controle pode estar em qualquer um dos estados internos do autômato, em 
um dado instante. A unidade de controle pode mudar de estado dependendo das funções de 
transições definidas. 
Um autômato pode ser representado por um grafo, onde os vértices (ou círculos) são os 
estados e as arestas (ou arcos) definem a função de transição. 
 
 Autômatos Finitos Determinístico (AFD) 
Aquele que se encontra em um único estado depois de ler uma seqüência qualquer de 
entradas. O termo determinístico se refere ao fato que, para cada entrada, existe um e 
somente um estado ao qual o autômato pode transitar a partir de seu estado atual. 
 
Um autômato finito determinístico, ilustrado na Figura 2, é definido pela quíntupla: 
M = (Q, Ʃ, δ, q0, F) 
Onde: Q – conjunto finito de estados 
 Ʃ – alfabeto de entrada (ou conjunto finito de símbolos) 
δ – função de transição (ou função programa, que toma como argumentos um estado 
e um símbolo de entrada e retorna um estado). É definida por δ: Q x Ʃ → Q 
q0 – estado inicial (q0 ϵ Q) 
F – conjunto de estados finais (F ϵ Q) 
 
Exemplo 1: Dado o autômato, especifique sua quíntupla. 
 
 
 
 
 
 
 
Figura 2. Autômato Finito Determinístico 
 
q0 q1 q2 
1 1 
0 
1 0 
0 
Aspectos Teóricos da Computação 
1º semestre 2019 3/7 
Tabela de Transição: é uma representação tabular de uma função como δ que recebe dois 
argumentos e retorna um valor. As linhas da tabela correspondem aos estados, e as colunas 
às entradas. O estado inicial é marcado com uma seta e os estados de aceitação são 
marcados com um asterisco. 
 
Exemplo 2: Desenhe o autômato sabendo que Ʃ = {w | w possui aa ou bb como subcadeia } 
e o autômato é dado por M = ({q0, q1, q2, qf}, {a, b}, δ, q0, {qf}), onde o δ está representado na 
tabela abaixo. 
 
δ a b 
q0 q1 q2 
q1 qf q2 
q2 q1 qf 
qf qf qf 
 
Dois Autômatos Finitos M1 e M2 são ditos equivalentes se, e somente se: L(M1) = L(M2); ou 
seja, reconhecem a mesma linguagem. 
 
 
 Autômatos Finitos não Determinístico (AFN) 
Um Autômato Finito não Determinístico tem o poder de estar em vários estados ao mesmo 
tempo. A diferença entre um AFD e um AFN está no tipo de δ. Para um AFN, δ é uma 
função que recebe um estado e um símbolo de entrada como argumentos, mas retorna um 
conjunto de zero, um ou mais estados (em vez de retornar exatamente um estado, como um 
AFD deve fazer) 
 
Um autômato finito não determinístico, ilustrado na Figura 3, é definido pela quíntupla: 
M = (Q, Ʃ, δ, q0, F) 
Onde: Q – conjunto finito de estados 
 Ʃ – alfabeto de entrada (ou conjunto finito de símbolos) 
δ – função de transição (ou função programa). É definida por δ: Q x Ʃ → 2Q 
q0 – estado inicial (q0 ϵ Q) 
F – conjunto de estados finais (F ϵ Q) 
Obs: 2Q - representa os subconjuntos de Q. 
 
Aspectos Teóricos da Computação 
1º semestre 2019 4/7 
Exemplo 3: Considere a linguagem L = { w | w possui aa ou bb como subcadeia }. O 
autômato finito não determinístico pode ser dado por: 
M = ( { q0, q1, q2, qf }, { a, b }, δ, q0, {qf} ) 
onde δ é como abaixo: 
δ(q0, a) = { q0, q1 } δ(q1, a) = qf δ(qf, a) = qf 
 δ(q0, b) = { q0, q2 } δ(q2, b) = qf δ(qf, b) = qf 
 
 
 
 
 
 
 
 
 
 
Figura 3. Autômato Finito Não Determinístico 
 
 
 Equivalência entre os Autômatos AFD e AFN 
Sabe-se que um autômato M1 é equivalente a um autômato M2 se, e somente se, L(M1) = 
L(M2). Então, pode-se transformar um AFN em AFD para que a linguagem lida pelo AFN 
seja do tipo regular. 
 
Seja M = (Q, Ʃ, δ, q0, F) um AFN qualquer. Seja M’ = (Q’, Ʃ, δ’, {q0}, F’) um AFD construído 
a partir de M como segue: 
Q’ – é o conjunto de todas as combinações, sem repetições, de estados de Q as 
quais são denotadas por {q1q2...qn}, onde qj pertence a Q para j em {1, 2, ..., n}. 
Note-se que a ordem dos elementos não distingue mais combinações. Por 
exemplo, {q1q2} = {q2q1}; 
 Ʃ – alfabeto de entrada (ou conjunto finito de símbolos); 
δ' – tal que δ’ ({q1...qn},a) = {p1...pm} se, e somente se, δ ({q1...qn},a) = {p1...pm}. Ou 
seja, um estado de M’ representa uma imagem dos estados de todos os 
caminhos alternativos de M; 
{q0 } – estado inicial; 
F’ – conjunto de todos os estados {q1q2...qn} pertencentes a Q’ tal que algum 
componente qj pertence a F, para j em {1, 2, ..., n}. 
Aspectos Teóricos da Computação 
1º semestre 2019 5/7 
Exemplo 4: Converta o seguinte AFN em um AFD: 
 
M = ({q0, q1, q2, qf}, {a,b}, δ, q0, {qf}) e 
 δ(q0, a) = {q0, q1} δ(q1, a) = q2 
δ(q0, b) = q0 δ(q2, a) = qf 
 
AFN: 
M = (Q, Σ, δ, q0, F) 
Q = { q0, q1, q2, qf } 
Σ = {a, b} 
q0 = q0 
F = { qf } 
 
AFD: 
M = (Q´, Σ´, δ´, q0´, F´) 
Q´ = { Ø , {q0}, {q1}, {q2}, {qf }, {q0, q1}, {q0, q2}, {q0, qf }, {q1, q2}, {q1, qf }, {q2, qf }, {q0, q1, q2}, 
 {q0, q1, qf }, {q0, q2, qf }, {q1, q2, qf }, {q0, q1, q2, qf } } 
Σ´ = {a, b} 
q0´= q0 
F´ = { { qf }, {q0, qf}, {q1, qf}, {q2, qf}, {q0, q1, qf}, {q0, q2, qf}, {q1, q2, qf}, {q0, q1, q2, qf} } 
 
 a b 
→ q0 {q0, q1} {q0} 
 q1 {q2} Ø 
 q2 {qf } Ø 
* qf Ø Ø 
 {q0, q1} {q0, q1, q2} {q0} 
 {q0, q2} {q0, q1, qf } {q0} 
* {q0, qf } {q0, q1} {q0} 
 {q1, q2} {q2, qf } Ø 
* {q1, qf } {q2} Ø 
* {q2, qf } {qf } Ø 
 {q0, q1, q2} {q0, q1, q2, qf } {q0} 
* {q0, q1,qf } {q0, q1, q2} {q0} 
* {q0, q2, qf } {q0, q1, qf } {q0} 
* {q1, q2, qf } {q2, qf } Ø 
* {q0, q1, q2, qf } {q0, q1, q2, qf } {q0} 
 a b 
→ q0 {q0, q1} {q0} 
q1 {q2} Ø 
q2 {qf } Ø 
* qf Ø Ø 
Aspectos Teóricos da Computação 
1º semestre 2019 6/7 
AFD Otimizado: 
 
 
 
 
 
 
 
 
 Autômato Finito com Movimentos Vazios 
Movimentos vazios constituem uma generalização dos modelos de máquinas não-
determinísticas. Um movimento vazio é uma transição sem leitura de símbolo algum da fita. 
Pode ser interpretado como um não determinismo interno ao autômato o qual é 
encapsulado, ou seja, excetuando-se por uma eventual mudança de estados, nada mais 
pode ser observado sobre um movimento vazio. Uma das vantagens dos Autômatos Finitos 
com Movimentos Vazios no estudo das linguagens formais é o fato de facilitar algumas 
construções e demonstrações relacionadas com os autômatos. 
No caso dos Autômatos Finitos, a facilidade de movimentos vazios não aumenta o poder de 
reconhecimento de linguagens. Qualquer Autômato Finito com Movimentos Vazios pode ser 
simulado por um Autômato Finito Não-Determinístico. 
 
Definição: Um Autômato Finito Não Determinístico com Movimentos Vazios (AFNξ) ou 
simplesmente Autômato Finito com Movimentos Vazios (AFξ) é uma quíntupla: 
M = (Q, Ʃ, δ, q0, F) 
onde: Q - é conjunto de estados possíveis do autômato o qual é finito; 
Ʃ - alfabeto de entrada (ou conjunto finito de símbolos); 
δ - função programa ou função de transição; 
q0 - estado inicial tal que q0 é elemento de Q; 
F - conjunto de estados finais tal que F está contido em Q. 
 
Figura 4. Representação como um grafo da função programa com movimentos vazios. 
{q0} 
 a a 
b 
a 
{q0, q1} 
b 
{q0, q1, q2} {q0, q1, q2, qf} 
a 
b 
b 
Aspectos Teóricos da Computação 
1º semestre 2019 7/7 
Portanto, excetuando-se pela função programa, as componentes Ʃ, Q, F e q0 são como na 
definição de AFN. Um movimento vazio (ou transição vazia) é representado pela aplicação 
da função programa, em um dado estado q ao símbolo especial ξ, ou seja, δ (q, ξ). A função 
programa com movimentos vazios pode ser interpretada como um grafo finito direto, como 
ilustrado na Figura 4, supondo que: 
δ(q, ξ) = {p0}, δ(q, a1) = {p1}, ..., δ(q, an) = {pn} 
 
O processamento de um AFξ é análogo ao de um AFN. Adicionalmente, o processamento 
de uma transição para uma entrada vazia também é não determinística. Assim, um AFξ ao 
processar uma entrada vazia assume simultaneamente os estados destino e origem. Ou 
seja, a origem de um movimento vazio sempre é um caminho alternativo. 
 
Exemplo:Considere a Linguagem: L = {w | qualquer símbolo a antecede qualquer símbolo b} 
 
O autômato finito com movimentos vazios: M = ({q0,qf}, {a,b}, δ, {q0}, {qf}) 
 
Figura 5. Grafo do Autômato Finito com Movimentos Vazios. 
 
A Figura 5 ilustra o autômato, onde δ é como abaixo, representada na forma de tabela, é tal 
que ACEITA(M) = L: 
 
δ a b ξ 
q0 {q0} - {qf} 
qf - {qf} - 
 
 
 
 
Referência: 
Menezes, Paulo Blauth. Linguagens Formais e Autômatos. 4ª Edição. Editora Sagra Luzzatto. Porto 
Alegre, 2001. 
 
Hopcroft, John E.; Ullman, Jeffrei D.; Motwani, Rajeev; Introdução À Teoria de Autômatos, 
Linguagens e Computação; 2ª edição; 2002; Ed Campus.