LINGUAGENS FORMAIS Modelos Determinísticos e Não ...palhares2.flu.angelfire.com/uniceub/tc/tct002.pdf · Autômato Finito Determinístico (AFD) → A função programa do AFN, ao

41

LINGUAGENS FORMAISModelos Determinísticos e Não Determinísticos

• Modelos Matemáticos

→ Usam-se modelos matemáticos para representareventos (fenômenos) do mundo real.

→ Ressalta-se contudo que é muito importante distiguirentre o fenômeno propriamente dito e o(s) modelo(s)matemático(s) usado(s) para representá-lo !!!

� “Todas as vezes que empregamos Matemática a fim deestudar alguns fenômenos de observação, devemosessencialmente começar por construir um modelomatemático (determinístico ou probabilístico) paraesses fenômenos. (...) A fim de verificar a validade deum modelo, devemos deduzir um certo número deconsequências de nosso modelo e, a seguir, compararesses resultados previstos (pelo modelo) comobservações efetuadas”.

(Prof. J. Neyman – University of California Publications in Statistics, Vol

I, University of California Press, 1954)

42


� Os modelos podem ser dois tipos: Determinísticos ouNão Determinísticos

Modelos Determinísticos

� Nos modelos determinísticos, os fenômenos sãorepresentados por um conjunto E = { e1, e2, ... en} devariáveis de entrada e um conjunto S = { s1, s2, ..., sk} devariáveis de saída cujos valores dependem dos valoresdas variáveis de entrada. O modelo é dito determinísticosempre que para uma determinada instância de E seproduz a mesma instância de S.

43


Modelos Determinísticos - Exemplo

� Espaço percorrido por um móvel à uma determinadavelocidade constante num determinado espaço detempo:

E = V * T

onde E = espaço (variável de saída),V = velocidade constante (variável de entrada)T = tempo decorrido do deslocamento do móvel(variável de entrada)

� Sempre que V = 80 Km/h e T = 2h, tem-se queE = 160 Km. ⇒ Modelo Determinístico !!!

44


Modelos Determinísticos - Exemplo

� Autômatos Finitos (AF). Porquê AFD ? Porquê otermo “determinístico” ?

� Note que em um AFD, se a “máquina” AF seencontra em determinado estado qk e na fita deentrada de dados for lida uma determinada primitivaa, então sempre o novo estado do AF é umdeterminado estado qm.

qk x a → qm

45


Modelos Não Determinísticos

� Nos modelos não determinísticos, os fenômenos sãorepresentados por um conjunto E = { e1, e2, ... en} devariávies de entrada e um conjunto S = { s1, s2, ..., sk} devariáveis de saída cujos valores dependem dos valoresdas variávies de entrada. O modelo é dito nãodeterminístico se para uma mesma determinada instânciade E é possível produzir instâncias distintas de S.

� Os modelos não determinísticos, em geral, estãoassociados a fenômenos probabilísticos (ouestocásticos).

Exemplo: Resultado do lançamento de uma moeda

46


Modelos Não Determinísticos - Exemplos

� Modelagem dos seguintes fenômenos (experimentos):

� Lançar um dado e observar o número mostrado na facede cima.

� Lançar uma moeda quatro vezes e observar o númerototal de caras obtido.

� Lançar uma moeda quatro vezes e observar asequência obtida de caras e coroas.

� Em uma linha de produção, fabricar peças em série econtar o número de peças defeituosas produzidas numperíodo contínuo de 24 horas.

� Em uma urna que contém 18 bolas pretas e 12 bolasazuis retirar ao acaso uma bola e anotar sua cor

� Fabricar uma lâmpada e colocá-la num soqueteanotando o tempo decorrido (em horas) até queimar

� Com base no banco de dados de compras de clientes deuma empresa, verificar, em quantos dias o estoque dedeterminada mercadoria será zerado.

47


Modelos Não Determinísticos - Exemplo

� Considerando-se a existência de “máquinas” AFD, épossível supor a existência e/ou construção deautômatos finitos não determinísticos (AFN) ?

� Sim, é possível “projetar” um autômato finito (AF)de modo que, se a “máquina” AF se encontra emdeterminado estado qk e na fita de entrada de dadosfor lida uma determinada primitiva a, então o AFpode assumir estados alternativos qm1, qm2, ... qmr.

48

LINGUAGENS FORMAISAutômato Finito Não Determinístico

• Autômato Finito Não Determinístico (AFN)

→ “Máquina” igual ao AFD composta de 3 partes:

a) Fita : dispositivo de entrada que contém a informação aser processada

b) Unidade de controle: Reflete o estado corrente damáquina. Possui uma unidade de leitura (cabeça da fita) aqual acessa uma célula da fita de cada vez e movimenta-se exclusivamente para a direita

c) Programa ou função de transição: função que comandaas leituras e define o estado (status) da máquina

49


Autômato Finito Não Determinístico (AFN)X

Autômato Finito Determinístico (AFD)

→ A função programa do AFN, ao processar uma entrada(estado corrente e símbolo lido) tem como resultadoum conjunto de novos estados: δ: Q x Σ → 2Q

→ Um AFN assume um conjunto de estados alternativos,como se houvesse uma multiplicação da unidade decontrole da “máquina”, uma para cada alternativa,processando independentemente, sem compartilharrecursos com as demais. Assim o processamento de um“caminho” não influencia nem é influenciado pelosdemais “caminhos”

50


• Autômato finito não determinístico (AFN) é uma 5-upla:

M = (Σ, Q, δ, q0, F)

Onde:

Σ Alfabeto de símbolo de entradaQ Conjunto de estados possíveis do autômatoδ Função programa ou função de transição

δ: Q x Σ → 2Q

q0 Estado inicial do autômato (Obs.: q0 ∈ Q )F Conjunto de estados finais tal que F ⊂ Q

• Processamento de um AFN M, para uma palavra(SENTENÇA) w de entrada ⇒ Sucessiva aplicação dafunção programa para cada símbolo de w (da esquerdapara a direita) até ocorrer uma condição de parada

• Após processar o último símbolo da palavra w “escrita”na fita, o AFN assume um estado em cada um dos“caminhos” obtidos . Se em ao menos um “caminho” oestado é um estado final, então o AFN aceita w.

51


52


53


→ Embora a facilidade de não-determinismo seja,aparentemente, um significativo acréscimo aoAutômato finito, na realidade não aumenta seu podercomputacional (em termos de reconhecimento)

→ AFD podem levar a reconhecedores mais rápidos queAFN. Contudo, AFD pode ser muito maior do que umAFN

→ Para cada AFN é possível construir um AFDequivalente que realiza o mesmo processamento.Também é possível construir a partir de um AFD, umAFN equivalente.

54

LINGUAGENS FORMAISAFN →→→→ AFD

Construção de um AFD a partir de um AFN

55

AFN →→→→ AFDConstrução de um AFD a partir de um AFN - Exemplo

56

Autômatos Finitos com Movimentos Vazios

→ Movimentos vazios ⇒ Generalização dos modelos demáquinas não-determinísticas

→ A facilidade de movimentos vazios não aumenta opoder de reconhecimento das linguagens

→ uso de movimentos vazios facilitam algumasconstruções e demonstrações relacionadas comautômatos

57

LINGUAGENS FORMAISAutômato Finito com Movimentos Vazios

• Autômato finito com movimentos vazios (AFε): 5-upla

M = (Σ, Q, δ, q0, F)

Onde:

Σ Alfabeto de símbolo de entradaQ Conjunto de estados possíveis do autômatoδ Função programa ou função de transição

δ: Q x (Σ ∪ {ε}) → 2Q

q0 Estado inicial do autômato (Obs.: q0 ∈ Q )F Conjunto de estados finais tal que F ⊂ Q

→ A partir de um AFε qualquer é possível construir umAFN que realiza o mesmo processamento

58

LINGUAGENS FORMAISAFN e AFεεεε - Exemplos

59


60


61

LINGUAGENS FORMAISAFD, AFN e AFεεεε

• Poder de reconhecimento “limitado”

→ Não dispõem de “memória”

→ Os estados da máquina representariam memória

62

LINGUAGENS FORMAISBrevíssima revisão do que foi visto

• Linguagem

� De modo resumido, podemos dizer que linguagem éum conjunto (finito ou não) de sentenças (Σ*)construídas sobre um determinado alfabeto (Σ).

• Sentença

� É formada pela justaposição (“colagem”) dos símbolosdo alfabeto Σ da linguagem em questão. É a sentençaque carrega “embutida em si” significadoscompreensíveis pelos usuários da linguagem.

• Gramática

� De modo resumido, gramática é o conjunto de regrasusadas que definem quais justaposições (“colagens”)podem ser realizadas com os símbolos do alfabeto Σ dalinguagem em questão para formação das sentenças damesma. Em última instância, é a “fábrica de sentenças”da linguagem.

63

LINGUAGENS FORMAISBrevíssima revisão do que foi visto

• Linguagens Regulares ( ou Lineares ou Tipo 3)

� Uma Linguagem L é dita ser uma Linguagem Regular(ou Linear ou Tipo 3) se existe uma Gramática RegularG tal que G gera todas as sentenças de L

� Uma Linguagem L é dita ser uma Linguagem Regular(ou Linear ou Tipo 3) se existe um AFD (ou AFN) Mtalque M reconhece todas as sentenças de L .

• Gramáticas Regulares ( ou Lineares ou Tipo 3)

� Uma Gramática G = (V,T,P,S) é Regular (ou Linear ouTipo 3) se todas suas regras de produção apresentamforma A → wB ou A → w onde A, B ∈ V e w ∈ T*

64

LINGUAGENS FORMAISGramáticas Tipo 3, 2, 1 e 0

• Gramáticas Regulares ( ou Lineares ou Tipo 3)

� Regras de produção com formato A → wB ou A → w onde A, B ∈ V e w ∈ T*

• Gramáticas Livres de Contexto ( ou Tipo 2)

� Regras de produção com formato A → α onde α ∈ (V ∪ T)*

• Gramáticas Sensíveis ao Contexto ( ou Tipo 1)

� Regras de produção com formato α → β onde α ∈ (V ∪ T)*, β ∈ (V ∪ T)* e |α| ≤ β|

• Gramáticas Irrestritas ( ou Tipo 0)

� Regras de produção com formato α → β onde α ∈ (V ∪ T)*, β ∈ (V ∪ T)*

• As gramáticas tipo 3, 2, 1 e 0 são as 4 classes degramáticas capazes de gerar 4 classes de linguagens, deacordo com a denominada hierarquia de linguagens deChomsk.

65

LINGUAGENS FORMAISGramáticas Tipo 3, 2, 1 e 0

• Observe que as gramáticas Tipo 3 (Regulares) são asmais restritivas: à esquerda da regra de produção deveconter uma e somente uma variável não terminal. Alémdisso, à direita da regra só pode ocorrer no máximo umavariável não terminal.

• As gramáticas Tipo 2 (Livre Contexto) são pouco menosrestritivas em relação às gramáticas Tipo 3. À esquerdada regra de produção deve, assim como na gramáticaTipo 3, conter uma e somente uma variável não terminal,mas, à direita da regra de produção, “o contexto é livre”,ou seja, não há restrições.

• As gramáticas Tipo 1 (Sensíveis ao Contexto) nãorestringem o conteúdo nem à esquerda, nem à direita dasregras de produção. Apenas exigem que o tamanho dos“componentes” à direita da regra de produção seja maiorque o tamanho de “componentes” à esquerda da regra deprodução.

• As gramáticas Tipo 0 (Irrestritas) não apresentamrestrição alguma no formato das regras de produção.Correspondem ao dispositivo mais abrangente de geraçãode linguagens.

66

LINGUAGENS FORMAISLinguagens Tipo 3, 2, 1 e 0

• As Gramáticas Tipo 3, 2, 1 e 0 geram, respectivamenteLinguagens Tipo 3, 2, 1 e 0

Gramática gera LinguagemTipo 3 (Regular) → Tipo 3 (Regular)Tipo 2 (Livre Contexto) → Tipo 2 (Livre Contexto)Tipo 1 (Sensível ao Contexto)→ Tipo 1 (Sensível ao Contexto)Tipo 0 (Irrestrita) → Tipo 0 (Irrestrita)

• As Linguagens Tipo 3, 2, 1 e 0 podem ser formalmentedefinidas, não somente por suas respectivas gramáticas,mas também por um tipo específico de reconhecedor.

� Os autômatos finitos (AFD ou AFN) reconhecemsentenças de linguagens Tipo 3 (linguagens regulares)

� Os autômatos de pilha (AP) reconhecem sentenças delinguagens Tipo 2 (linguagens de livre contexto)

� As Máquinas de Turing com fita limitada reconhecemsentenças de linguagens Tipo 1 (linguagens Sensíveisao Contexto)

� As Máquinas de Turing reconhecem sentenças delinguagens Tipo 0 (linguagens recursivamenteenumeráveis)

67

LINGUAGENS FORMAISLinguagens Tipo 3, 2, 1 e 0

• Asociação entre classes de linguagens, gramáticas ereconhecedores

Linguagem Gramática ReconhecedorTipo 3:Regular

Tipo 3:Regular

Autômatos finitos(AFD ou AFN)

Tipo 2:Livre Contexto

Tipo 2:Livre Contexto

Autômatos dePilha

Tipo 1:Sensíveis ao

contexto

Tipo 1:Sensíveis ao

contexto

Máquina de Turingcom fita limitada

Tipo 0:Recursivamente

enumerável

Tipo 0:Irrestrita

Máquina de Turing

68

LINGUAGENS FORMAISLinguagens de Livre Contexto (Tipo 2)Reconhecedores - Autômatos de Pilha

69

70

71

72

73

74

75

76

77

LINGUAGENS FORMAISMáquina de Turing - Caracterização “rigorosa”

78


79


80


81

LINGUAGENS FORMAISMáquina de Turing - Exercícios

1) Projete uma Máquina de Turing sobre o alfabeto Σ = {0,1} que reconheça sentenças w da linguagem L onde

L = { w | w possui número igual de primitivas 0 e 1 }


L = { w | w é palíndroma }

3) Projete uma Máquina de Turing sobre o alfabeto Σ = {0,1} que reconheça sentenças da linguagem L onde L ={ wwR }. Obs.: R significa “reverso”. Exemplo: se w =0100, então wwR = 01000010


L = { w | w = 0n1m onde n ≥ m ≥ 1 }


L = { w | w = 0n12n onde n ≥ 0 }

82


6) Projete uma Máquina de Turing sobre o alfabeto Σ ={a,b,c} que reconheça sentenças w da linguagem L onde

L = { w | w = aibkcm onde i ≥ 1,k ≥ 1,m ≥ 1 }


L = { w | w = aibkcm onde i = k ou i = m mas k ≠ m }


L = { w | w = anbncn onde n ≥ 1 }


L = {w | w possui o mesmo número de símbolos a, b e c}

10) Projete uma Máquina de Turing sobre o alfabeto Σ ={a,b} que reconheça sentenças w da linguagem L onde

L = { w | w = anbnan+m onde n ≥ 0 e m ≥ 0 }

83



L = { ww | w é palavra de {a,b}* }


L = {(awwa)n | w é palavra de {a,b}* e n ≥ 0 }


L = {w | w = a1b2a3b4...an-1 bn e n é par }

14) Execução de soma de número binário: projete umaMáquina de Turing sobre o alfabeto Σ = {0, 1} queadicione 1 ao número binário (sentença w) que estáarmazenado na fita da MT.

15) Projete uma Máquina de Turing para computar afunção

84


16) Execução de “multiplicação” de uma sentença w = 0m.projete uma Máquina de Turing sobre o alfabeto Σ = {0,1} que “multiplique” a sentença n vezes, conforme aindicação 0n. Inicialmente a fita se encontra assim:0m10n1. Note então que o símbolo 1 é um separador dos“operandos” 0m e 0n.

Exemplo: Fita inicialmente: 000100001. Após a“multiplicação” a fita fica assim: 000000000000. (Emresumo, 3 x 4 = 12 !!)

17) Projete uma Máquina de Turing sobre o alfabeto Σ ={a,b,c,d} que reconheça sentenças w da linguagem Londe

L = {w | w = apbmap+3bm-1 , onde p ≥ 0 e m ≥ 1 }

Documents

LINGUAGENS FORMAIS Modelos Determinísticos e Não ...palhares2.flu.angelfire.com/uniceub/tc/tct002.pdf · Autômato Finito Determinístico (AFD) → A função programa do AFN, ao