Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 78 vistas

    Trabajos Prácticos SSL 2020

    Cargado por

    Ignacio Valente
    El documento presenta 17 ejercicios sobre gramáticas formales y lenguajes formales. Los ejercicios incluyen definir cadenas pertenecientes a conjuntos, derivaciones a la derecha e izquierda, reglas de producción para gramáticas que reconozcan lenguajes específicos, y diagramas de derivación de cadenas. Los ejercicios cubren temas como vocabularios, conjuntos de producción, gramáticas regulares y no regulares, y reconocimiento de lenguajes formales.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd

    Trabajos Prácticos SSL 2020

    Cargado por

    Ignacio Valente
    78 vistas4 páginas
    El documento presenta 17 ejercicios sobre gramáticas formales y lenguajes formales. Los ejercicios incluyen definir cadenas pertenecientes a conjuntos, derivaciones a la derecha e izquierda, reglas de producción para gramáticas que reconozcan lenguajes específicos, y diagramas de derivación de cadenas. Los ejercicios cubren temas como vocabularios, conjuntos de producción, gramáticas regulares y no regulares, y reconocimiento de lenguajes formales.

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    DOCX, PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    El documento presenta 17 ejercicios sobre gramáticas formales y lenguajes formales. Los ejercicios incluyen definir cadenas pertenecientes a conjuntos, derivaciones a la derecha e izquierda, reglas de producción para gramáticas que reconozcan lenguajes específicos, y diagramas de derivación de cadenas. Los ejercicios cubren temas como vocabularios, conjuntos de producción, gramáticas regulares y no regulares, y reconocimiento de lenguajes formales.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    78 vistas4 páginas

    Trabajos Prácticos SSL 2020

    Cargado por

    Ignacio Valente
    El documento presenta 17 ejercicios sobre gramáticas formales y lenguajes formales. Los ejercicios incluyen definir cadenas pertenecientes a conjuntos, derivaciones a la derecha e izquierda, reglas de producción para gramáticas que reconozcan lenguajes específicos, y diagramas de derivación de cadenas. Los ejercicios cubren temas como vocabularios, conjuntos de producción, gramáticas regulares y no regulares, y reconocimiento de lenguajes formales.

    Copyright:

    © All Rights Reserved
    Descargue como DOCX, PDF, TXT o lea en línea desde Scribd
    Descargar como docx, pdf o txt
    de 4

    Trabajos Prácticos

    1. Gramáticas y lenguajes formales

    1) Sea el vocabulario V={1,2}. Indique cinco de las cadenas pertenecientes a V* y


    V+.

    V*: 1112, 121212, 12211, 112211, 122

    V+: 222,11,212,1112,21222

    2) Sean los vocabularios V={i,x} y W={i,v,c}. Defina por extensión:

    a) V3 = V . V . V= {iii,iix,ixi,ixx,xii,xix,xxi,xxx}
    b) W*= W0 U W1 U W2… (a infinito).
    c) V. W= {ii,iv,ic,xi,xv,xc}

    3) Sea {000 ->010, 10 -> 01} para la palabra “1010”, obtenga las derivaciones a la
    derecha.

    1010->1001->0101->0011

    4) Sea {000 ->010, 10 -> 01} para la palabra “1010”, obtenga las derivaciones a la
    izquierda.

    1000 -> 0100 -> 0010 -> 0001 -> 0101 -> 0011

    5) Defina los conjuntos P de la gramática de G = {{0,1},{S,A,B,C} , S, P} que


    reconozca : 001010

    S ::= 0A0

    A::= 0B1

    B::=1C0

    C::= λ

    6) Defina los conjuntos P de la gramática de G = {{0,1},{S,A,B,C} , S, P} que


    reconozca : 000101

    S::= 0A1
    A::=0B0
    B::=0C1
    C::= λ

    7) Definir las reglas de una gramática tipo 2 en base a la especificación dada que
    reconozca el lenguaje:
    L1 = {wncwn/ w ε {a,b} n > 0}
    G1 = ({a,b,c} , {A,S} , P, S)

    P:
    S::= aAa |bAb
    A::= aAa|bAb|c
    8)
    9) Defina las reglas de producción para el lenguaje: L1 = {a n c bm /n > 0 y m >= 0 }

    S::=aA
    A::=aA|Ab|aAb|c

    10) Para la especificación dada dibuje el árbol de derivación para: aacbb

    P = {e0 -> a e1, e1 -> a e1 | c e2, e2 -> be2}


    e0
    ae1
    ae1
    ce2
    be2
    be2
    λ

    11) Sea la cuádrupla es G = ({S,A,B}, {0,1} , P, S} con el siguiente conjunto de


    producciones, indique 3 cadenas validas diferentes y dibuje los respectivos
    árboles de derivación:

    P : {S  A1B, A 0A | λ, B  0B | 1B | λ }

    SA1B0A10B0λ10λ010
    SA1Bλ11B λ11λ11
    S A1B λ1λ1

    S S S

    A1B A1B A1B

    0A 0B λ 1B λ λ

    λ λ λ

    12) Dibuje el árbol de derivación para la cadena z=(x+y)*z correspondiente a la


    siguiente gramática:

    ASSIGN  ID ‘=’ EXPR


    ID  ‘x’|’y’|’z’
    EXPR  ID ‘+’ EXPR | EXPR ‘*’ ID | ‘(‘EXPR’)’|ID

    ASSIGN

    ID ‘=’ EXPR

    ‘z’ EXPR ‘*’ ID

    ‘(‘EXPR’)’ ‘z’

    ID ‘+’ EXPER

    ‘x’ ID

    ‘y’
    13) Verificar si la siguiente gramática genera cadenas ambiguas, en cuyo caso dar
    los ejemplos.

    G = ({‘a’,’+’,’*’,’(’,’)’, {S}, S, P}
    P = {S::= ‘a’, S::= S’+’S, S::= S*S, S::= S}

    SS+Sa+Sa+a
    SSS+Sa+Sa+Sa+a

    14) Construya una gramática regular no ambigua que genere todas las cadenas de
    0 y 1 en las cuales 0, si aparecen lo hacen en grupos individuales de tres.

    G=({S, A},{1,0},S,P)

    P=( S1S | 000A | λ , A 1S | λ )

    15) Escriba las reglas de producción para la gramática G1, no ambigua, que
    reconoce el lenguaje L1 = {wcwR / w E { a | b} } y R>=0}

    G1= ({A},{a,b,c},P, S1)

    P = (S1  wa , a

    16) Completar las reglas de producción para la gramática. Sea G1= ({A,B},{a},P, S)
    una gramática regular lineal a derecha que genera L = {a 2n /n >=0}

    Sλ S aA
    A  aB Aa
    B  aaS
    17) Completar las reglas de producción para la gramática.

    G1= ({A,B,C},{0,1,2,3},P, S) que genera L= {0 i1i+k2k3n+1 / i, k, n > = 0}

    S ABC S3

    S  BC S 01

    A  0A1 A01

    B  1B2 B 12

    C  3C C 3

    También podría gustarte