Máquina de Turing com Fita Limitada

Autores: Patrícia Teixeira Davet e Thiago Ferreira Pontes

Professora: Simone Costa

Instituição: UFPEL – PPGC

Abril de 2014

Teoria da Computação

2

Introdução

Definição do Modelo

Exemplos

Referências

Tópicos

Máquina de Turing com Fita Limitada

3

Características

Limitação no tamanho da fita

Não determinística

Reconhecedora de Linguagens Sensíveis ao Contexto(LSC) – Tipo 1

Introdução

Máquina de Turing com Fita Limitada

4

Características

Extensões em relação aos autômatos finitos ou aosautômatos de pilha

Comprimento igual ao da cadeia de entrada, acrescidode duas células que contém os símbolos de início e fimda fita.

Deslocamento para direita e esquerda.

Leitura e escrita na fita.

Introdução

Máquina de Turing com Fita Limitada

5

Formalismo

M = (∑, Q, Г, δ, q0, F, <, >) onde:

∑ é o alfabeto de entrada, possui um número finito de símbolos;

Q é o conjunto finito de estados;

Г é o conjunto finito de símbolos que podem ser lidos e/ou gravados na fita detrabalho, ∑ ⊆ Г;

δ é a função parcial de transição , compreendendo os seguintes mapeamentos:

q0 é o estado inicial, q0 є Q;

F é o conjunto de estados finais, F ⊆ Q;

<, > são marcadores respectivamente de início e fim da fita, <, > ∉ Г .

Definição do Modelo

Máquina de Turing com Fita Limitada

6

Exemplo 1

M = (∑, Q, Г, δ, q0, F, <, >) que aceita a L= a*b*

MTFL = ({a,b}, {q0,q1,q2}, {a,b}, δ, q0, {q2}, <, >)

Diagrama de estados da MTFL:

Exemplos

Máquina de Turing com Fita Limitada

7

Exemplo 1

Teste 1: a cadeia ”aabbb‟ é aceita pela MTFL

Exemplos

Máquina de Turing com Fita Limitada

8

Exemplo 1

Teste 2: a cadeia ”aaba‟ não é aceita pela MTFL

Exemplos

Máquina de Turing com Fita Limitada

9

Exemplo 2

M = (∑, Q, Г, δ, q0, F, <, >) que aceita a L=

MTFL = ({a,b}, {q0,q1,q2q3,q4,q5,}, {a,b,X,Y}, δ, q0, {q4}, <, >)

Exemplos

Máquina de Turing com Fita Limitada

10

Exemplo 2

Teste 1:”aabb“ é aceita

Exemplos

Máquina de Turing com Fita Limitada

11

Exemplo 2

Teste 2:”aab“ não é aceita

Teste 3:”abb“ não é aceita

Exemplos

Máquina de Turing com Fita Limitada

12

[1] Ramos, M, V, M – Linguagens Sensíveis ao Contexto– Universidade Federal do Vale do São Francisco, 2010.

[2] P. Blauth Menezes – Linguagens Formais e Autômatos - UFRGS

Referências

Máquina de Turing com Fita Limitada

Máquina de Turing com Fita Limitada

Autores: Patrícia Teixeira Davet e Thiago Ferreira Pontes

Professora: Simone Costa

Instituição: UFPEL – PPGC

Abril de 2014

Teoria da Computação