Primer Recuperatorio 2C 2006 (Teoría de Lenguajes)

De Cuba-Wiki
Saltar a: navegación, buscar

Enunciado[editar]

Ejercicio 2[editar]

Sea

  1. Dar una gramatica libre de contexto para L
  2. Dar un automata de pila deterministico para L


Respuestas[editar]

Ejercicio 2[editar]

Gramática G = <Vn, Vt, S, P> donde:

  • Vn = {S, F, E, E'}
  • Vt = {a, b}
  • P esta dado por
    • S => F E
    • E => a E' b
    • E' => a E' b | lambda
    • F => aF | bF | lambda


Autómata de pila deterministico M dado por el siguiente grafo (incompleto), siendo q0 inicial, q3 final, Z simbolo inicial de la pila, q0 a q3 estados, {a,b} alfabeto de entrada, {A,B,Z} alfabeto de la pila y L representa lambda:

<graphviz> digraph G { rankdir="LR"; graph [ranksep = 1.5, nodesep=2]; node [shape=circle,fontname=Helvetica,fontsize=12]; node [width=0.5,height=0.5,fixedsize=true]; edge [fontname=Helvetica,fontsize=10];

q0 [label="q0"] q1 [label="q1"] q2 [label="q2"] q3 [label="q3", shape=doublecircle]

q0 -> q0 [label="b,Z | Z"] q0 -> q1 [label="a,Z | AZ"] q1 -> q1 [label="a,A | AA"] q1 -> q2 [label="b,A | L"] q2 -> q2 [label="b,A | L"] q2 -> q1 [label="a,A | AZ\na,Z | AZ"] q2 -> q3 [label="b,Z | Z"] q3 -> q1 [label="a,A | AZ\na,Z | AZ"] q3 -> q0 [label="b,Z | Z"] } </graphviz>