¿Cuál de las siguientes elementos no es parte de la definición formal de una gramática ? V -> conjunto de no terminales X -> orden de derivación de las reglas S ->Símbolo inicial.
¿Cuál de las siguientes elementos no es parte de la definición formal de una gramática ? V ->Conjunto de terminales X ->Símbolo inicial S ->Función de derivación.
¿Cuál de las siguientes gramáticas está en forma normal de Chomsky? E -> E + T
E -> T
T-> T * F
T -> F
F -> id S -> AB
A -> 1A
B -> 0B E -> EX
X -> BT
B -> +
T -> TY
Y -> ZF
Z -> *
F -> id.
¿Cuál de las siguientes gramáticas está en forma normal de Chomsky? S -> AB
A -> 1A
B -> 0 S -> AB
A -> 1
B -> 0 S -> AB
A -> 1A
B -> 0B.
¿Cuál de las siguientes gramáticas permite crear la sentencia: locomotora vagon vagon vagon? "<TREN> --> locomotora <RESTOTREN>
<RESTOTREN> --> vagon <RESTOTREN>
<RESTOTREN> --> vagon" "<TREN> --> locomotora <RESTOTREN>
<LOCOMOTORA> --> locomotora
<RESTOTREN> --> vagon
<RESTOTREN> --> vagon vagon" "<TREN> --> locomotora <RESTOTREN>
<LOCOMOTORA> --> locomotora
<RESTOTREN> --> vagon
<RESTOTREN> --> vagon".
¿Cuál de las siguientes gramáticas permite generar cadenas de unos y ceros alternados? X -> XY10
X -> 1
Y -> 0
X -> vacio X -> 10X
X -> vacio X -> 1Y0
Y -> 0X0
Y -> vacio.
¿Cuál de las siguientes gramáticas permite generar cadenas que contengan la misma cantidad de unos y de ceros? S --> ASB
A --> 1
B --> 0
S --> vacío S --> 0B
B --> 1AB
A --> 0
B --> vacío S --> AB
A --> 1B
B --> 0A
B --> vacío.
¿Cuál de las siguientes gramáticas permite generar una sentencia para declarar variables como la siguiente?. int a,b,c; VAR -> TIPO LISTA ;
TIPO -> int
TIPO -> char
LISTA -> id
LISTA -> id , LISTA VAR -> int VARIABLES
VAR -> char VARIABLES
VARIABLES -> id, VARIABLES ;
VARIABLES -> id , VARIABLES -> int LISTAVAR
VARIABLES -> char LISTAVAR
LISTAVAR -> id, VARIABLES
LISTAVAR -> id.
¿Cuál de los siguientes autómatas de pila permite reconocer cadenas que alternen letras a y b?: (q1, “a”, vacio) --> (q1, X)
(q2, “b”, vacio) --> (q2, y). (q1, “a”, X) --> (q1, YX)
(q2, “b”, Y) --> (q2, vacio). (q1, “a”, X) --> (q2, YX)
(q2, “b”, Y) --> (q1, vacio).
¿Cuál de los siguientes componentes no es parte de la definición formal de un autómata de pila? Conjunto de estados Alfabeto dual Función de transición.
¿Cuál de los siguientes componentes no es parte de la definición formal de un autómata de pila? Un conjunto finito de estados Alfabeto de transición Símbolo inicial.
¿Cuál de los siguientes conjuntos abarca el concepto de gramática? Conjunto de símbolos Conjunto de reglas Conjunto de terminales.
¿Qué es lo que diferencia a un autómata de pila de un autómata finito? La capacidad de entrada La capacidad para recordar La inclusión de una función de transición.
¿Un autómata de pila? Permite reconocer símbolos Permite reconocer cadenas Permite reconocer expresiones.
¿Un autómata de pila? Tiene dos memorias adicionales Recuerda los símbolos y estados recorridos Tiene una función de transición compartida.
Al transformar una gramática a forma normal de Chomsky la eliminación de símbolos inútiles significa: Eliminar un símbolo que no cumpla ninguna función a pesar de formar parte de la gramática Eliminar una regla que vaya a vacío Eliminar la parte izquierda de una regla siempre y cuando este símbolo sea no terminal.
Cada regla de la función de transición de un autómata de pila tiene dos partes, la parte derecha está formada por: Cima de la pila, estado origen Estado origen, Valor a escribir en la cima de la pila Estado destino, Valor a escribir en la cima de la pila.
Con la gramática:
S --> aSb
S --> b
¿Cuál de las siguientes sentencias no se puede generar? aaabbbb aabb aaaabbbbb.
Dada la gramática :
IFC -> IF ELSE
IF -> if (condicion) B
B -> sentencia
ELSE -> else B
¿Cuál de las siguientes cadenas SI puede ser generada? “if condicion sentencia” “if (condicion) sentencia else sentencia ” “if (condicion) sentencia”.
Dada la gramática :
S -> Ab
A -> b
A -> a
¿Cuál de las siguientes cadenas no puede ser generada? “ab” “bb” “ba”.
Dada la gramática :
S -> ASB
S -> A
A -> a
A -> vacio
B -> b
Elabore los árboles de derivación necesarios y determine ¿Cuál de las siguientes cadenas no puede ser generada? “b” “ab” “a”.
Dada la gramática :
S -> aSb
S -> BaC
B -> a
C -> b
Elabore los árboles de derivación necesarios y determine ¿Cuál de las siguientes cadenas puede ser generada? “aaaabbbb” “aaaabbb” “aaabbbb”.
Dada la gramática :
S -> aSb
S -> BC
B -> a
C -> b
Elabore los árboles de derivación necesarios y determine ¿Cuál de las siguientes cadenas puede ser generada? “aaaaabbbb” “aaabbb” “aaaabbbb”.
Dada la gramática siguiente:
E -> E + T
E -> T
T -> T * F
T -> F
F -> numero (numero es un terminal)
¿Cuál de las siguientes cadenas no se puede generar? numero + numero numero + (numero * numero) numero * numero + numero.
Dada la gramática siguiente:
E -> E + T
E -> T
T -> T * F
T -> F
F -> numero (numero es un terminal)
F -> (E)
Elabore los árboles de derivación necesarios y determine ¿Cuál de las siguientes cadenas no se puede generar? (numero * numero) * (numero * numero) (numero ) + numero + numero (numero) * numero) + (numero numero).
Dada la gramática siguiente:
E -> E + T
E -> T
T -> T * F
T -> F
F -> valor (valor se puede reemplazar por cualquier número)
¿Cuál de las siguientes cadenas no se puede generar? 4 + 6 3 - 7 9 + 4 * 7.
Dada la gramática siguiente:
E -> E + T
E -> T
T -> T * F
T -> F
F -> valor (valor se puede reemplazar por cualquier número)
¿Cuál de las siguientes cadenas no se puede generar? 4 + 6 3 * 7 2 * 3 - 2.
Dada la gramática siguiente:
S -> int M B
M -> main
B -> U
B -> U B
U -> a;
¿Cuál de las siguientes sentencias no puede ser generada? int main a int main a; a; int main a; a; a;.
Dada la Gramática X -> X a B
Al convertirla en forma normal de Chomsky, ¿Cuál sería el resultado? X -> XY
X-> a
Y-> b X-> XY
Y-> a X->XZ
Z->AB
A->a.
Dada la gramática
<FOR> ---> for (id=val; id <OPRELACIONAL> id; id++) <BLOQUE>
<OPRELACIONAL> ---> <
<OPRELACIONAL> ---> >
<OPRELACIONAL> ---> ==
<BLOQUE> ---> <UNASENTENCIA> <BLOQUE>
<BLOQUE> ---> <UNASENTENCIA>
<UNASENTENCIA> ---> id++
¿Cuál de las siguientes sentencias se puede generar? For (a=1; a<10; a++)
C++
D++
E++ For (a=1; a<10; a++)
C++;
D++;
E++; For (a=1, a<10, a++)
C++
D++
E++.
Dada la Gramática
BLOQUE -> UNASENTENCIA BLOQUE
BLOQUE -> UNASENTENCIA
UNASENTENCIA -> id++
Al convertirla en forma normal de Chomsky, ¿Cuál sería el resultado? BLOQUE -> UNASENTENCIA BLOQUE
BLOQUE -> UNASENTENCIA
UNASENTENCIA -> id++ BLOQUE -> UNASENTENCIA BLOQUE
UNASENTENCIA -> id++ BLOQUE -> UNASENTENCIA BLOQUE
BLOQUE -> UNASENTENCIA.
Dada la Gramática
E -> E + T
Al convertirla en forma normal de Chomsky, ¿Cuál sería el resultado? E -> E +
E -> + T
E -> T E -> E X
X -> + T E -> E X
X -> Y T
Y -> +.
Dada la Gramática
S -> aB.
Al convertirla en forma normal de Chomsky, ¿Cuál sería el resultado? S -> AB
A -> a S -> A
A -> a S -> a.
Dada la Gramática
S -> ABC
Al convertirla en forma normal de Chomsky, ¿Cuál sería el resultado? S -> AB
B ->BC S -> A
S -> B
B ->BC S -> aA
A ->BC.
Dada la Gramática
S -> main BLOQUE.
BLOQUE -> id++
Al convertirla en forma normal de Chomsky, ¿Cuál sería el resultado? S -> MAIN BLOQUE
MAIN -> main
BLOQUE -> id++ S -> main BLOQUE
BLOQUE -> SENTENCIA
SENTENCIA -> id++ S -> MAIN SENTENCIAS
MAIN -> main
SENTENCIAS -> B.
Dada la Gramática
VAR -> TIPO LISTA ;
TIPO -> int
LISTA -> id
Al convertirla en forma normal de Chomsky, ¿Cuál sería el resultado? VAR -> TIPO RESTO
TIPO -> int
RESTO -> A ;
A -> id VAR –> TIPO LISTA
TIPO -> int
LISTA -> ID FIN
ID -> id
FIN -> ; VAR ->TIPO RESTO
TIPO -> int
RESTO -> id ;.
Dada la siguiente gramátic
a. ¿Cuál de las siguientes sentencias de un lenguaje de programación puede generarse?
W -> while (CONDICION) BLOQUE
CONDICION -> id OPRELACIONAL id
BLOQUE -> UNASENTENCIA ; BLOQUE
BLOQUE -> UNASENTENCIA;
UNASENTENCIA -> id INCREMENTO
INCREMENTO -> ++
OPRELACIONAL -> >
OPRELACIONAL -> <
OPRELACIONAL -> == while a > b
a++;
b++; while (a > b)
a++; while (a > b)
a++;
b++;
c++;.
Dada la siguiente gramática S -> int M B
M -> main
B -> U
B -> U B
U -> F
U -> id++;
F -> for (id=val; id < val; id++) B
¿Cuál de las siguientes sentencias no puede ser generada? int main for (a=5;a<20;a++) x++; int main for (a=5;a<20;a++) x++; x++; int main a++; a++; a++.
Dada la siguiente gramática
W -> while ( COND ) BLOQUE
COND -> id OPERADOR id
OPERADOR -> COMPARADOR
COMPARADOR -> >
COMPARADOR -> <
COMPARADOR -> ==
BLOQUE -> UNASENTENCIA, BLOQUE
BLOQUE -> vacío
¿en que regla se encuentra un símbolo inútil? Regla 3 Regla 6 Regla 8.
Dada la siguiente gramática:
E -> E +T
E -> T
T -> T * F
T -> F
F -> id
Si se requiere eliminar las producciones unitarias, ¿Qué conjuntos de reglas hay que eliminar? Regla 2, regla 3, regla 4 Regla 1, regla 2, regla 3 Regla 2, regla 4, regla 5.
Dada la siguiente gramática:
Regla 1: IFC -> IF ELSE
Regla 2: IF -> if (condicion) B
Regla 3: B -> sentencia
Regla 4: ELSE -> else B
En la siguiente sentencia:
if condicion sentencia else sentencia
¿Cuál es el error? No correctamente se aplica regla 2 No correctamente se aplica regla 3 No correctamente se aplica regla 1.
Dada la siguiente gramática:
S -> AB
A -> aAA
A -> vacío
B -> bBB
Para que la gramática quede en forma normal de Chomsky es necesario eliminar las producciones vacías, en este caso, ¿Qué regla hay que eliminar? Regla 2 Regla 3 Regla 4.
Dada la siguiente gramática:
S -> AB
A -> C
C -> 1
B ->0
Si se requiere eliminar las producciones unitarias, ¿Qué regla hay que eliminar? Regla 2 Regla 3 Regla 4.
Dada la siguiente gramática:
W -> while ( COND ) BLOQUE
COND -> id OPERADOR id
OPERADOR -> COMPARADOR
COMPARADOR -> >
COMPARADOR -> <
COMPARADOR -> ==
BLOQUE -> UNASENTENCIA
UNASENTENCIA -> W
Si se requiere eliminar las producciones unitarias, ¿Qué conjuntos de reglas hay que eliminar? Regla 2, regla 6 Regla 3, regla 7 Regla 1, regla 8.
Dada la siguiente gramática:
W -> while ( COND ) BLOQUE
COND -> id OPERADOR id
OPERADOR -> COMPARADOR
COMPARADOR -> >
COMPARADOR -> <
COMPARADOR -> ==
BLOQUE -> vacío
BLOQUE -> UNASENTENCIA, BLOQUE
Para que la gramática quede en forma normal de Chomsky es necesario eliminar las producciones vacías, en este caso, ¿Qué regla hay que eliminar? Regla 3 Regla 7 Regla 8.
Dado el siguiente autómata de pila, al momento de reconocer una cadena el autómata:
(q1, “1”, X) -> (q1, ZX)
(q2, “0”, Z) -> (q2, vacío)
(q3, “#”, X) -> (q3, reconoce) No pasa de un estado a otro Pasa por todos los estados Permanece en el estado 2.
Dado el siguiente autómata de pila, para que reconozca la cadena “abc#” ¿Qué error debe corregirse?
(q1, “a”, X) -> (q2, ZX)
(q2, “b”, Z) -> (q2, vacío)
(q3, “c”, X) -> (q4, ZX)
(q4, “#”, Z) -> (q4, reconoce) Regla 3 debe ir desde q3 a q3 Regla 2 debe ir desde q2 a q3 Regla 4 debe terminar en q3.
Dado el siguiente autómata de pila:
(E1, “a”, X) -> (E2, ZX)
(E2, “b”, Z) -> (E3, vacío)
(E3, “c”, X) -> (E4, ZX)
(E4, “#”, Z) -> (E4, reconoce)
Se necesita reconocer la cadena “abc”# (#indica que la cadena termina)
Al ejecutar el autómata, el resultado es: Se reconoce la cadena No se puede reconocer la cadena La regla 2 debe enviar al estado E3.
Dado el siguiente autómata de pila:
(q1, “0”, X) -> (q2, ZX)
(q2, “1”, Z) -> (q1, vacío) Puede reconocer la cadena “010” Puede reconocer la cadena “101” Ninguna de las respuestas.
Dado el siguiente autómata de pila:
(q1, “0”, X) -> (q2, ZX)
(q2, “1”, Z) -> (q2, vacío) Puede reconocer la cadena “1010” y al final la pila queda con ZX Puede reconocer la cadena “010” y al final la pila queda con ZX No puede reconocer la cadena “010” por que la pila queda vacía.
Dado el siguiente autómata de pila:
(q1, “1”, X) -> (q1, ZX)
(q2, “0”, Z) -> (q2, vacío)
(q3, “#”, X) -> (q3, reconoce) No puede reconocer el segundo símbolo Reconoce toda la cadena Solo reconoce los símbolos “1” de la cadena.
Dado el siguiente autómata de pila:
(q1, “1”, X) -> (q2, ZX)
(q2, “0”, Z) -> (q2, vacío)
(q3, “#”, X) -> (reconoce) Reconoce cadenas del tipo “1010” No reconoce cadenas de tipo “1010” No pasa del estado q2 al estado q3.
Dado el siguiente autómata de pila:
(q1, “1”, X) -> (q2, ZX)
(q2, “0”, Z) -> (q2, vacío) Puede reconocer la cadena “1010” y al final la pila queda con ZX Puede reconocer la cadena “1010” y al final la pila queda con X No puede reconocer la cadena “1010” por que la pila queda vacía.
Dado el siguiente autómata de pila:
Regal 1: (q0, 1, Z) → (q1, Z)
Regla 2: (q0, 0, Z) →(q1, Z)
Regla 3: (q1, 1, Z) →(q0, Z)
Regla 4: (q1, 0, Z) → (q0, Z) Se reconocen cadenas que empiezan con 1 Se reconocen cadenas que empiezan con 0 Se reconocen cadenas que empiecen con 1 o con 0.
Dado el siguiente autómata, ¿Cuál de los siguientes cadenas se puede reconocer?: (q1, “a”, X) --> (q1, YX)
(q2, “b”, Y) --> (q2, vacio) “ababa” “abab” ninguna.
Dado el siguiente autómata, ¿Cuál de los siguientes cadenas se puede reconocer?:
(q1, “a”, X) --> (q2, YX)
(q2, “b”, Y) --> (q1, vacio) “ababac” “abab" “abc”.
De las siguientes cual no es una diferencia válida entre símbolos terminales y No Terminales: Terminales son hojas y los No terminales son padres Terminales se escriben con minúscula y terminales con mayúscula Terminales son axiomas y No terminales son no lo son.
De las siguientes reglas, ¿Cuál cumple los requisitos para estar en forma normal de Chomsky? OPERADOR ->> OPERADOR -> id > id OPERADOR -> id == id.
De las siguientes reglas, ¿Cuál cumple los requisitos para estar en forma normal de Chomsky? S -> a S -> ab S -> abc.
De las siguientes reglas, ¿Cuál cumple los requisitos para estar en forma normal de Chomsky? S ->A S -> AB S -> ABC.
De las siguientes reglas, ¿Cuál cumple los requisitos para estar en forma normal de Chomsky? S ->AB S -> Bc S -> Abc.
De las siguientes reglas, ¿Cuál cumple los requisitos para estar en forma normal de Chomsky? S ->ABC S -> aB S -> a.
De las siguientes reglas, ¿cuál es la más apropiada para reconocer un símbolo 1 y registrar su reconocimiento en la pila? (q1, “0101”, Y) -> (q2, 1X) (q1, “1”, X) -> (q2, 1X) (q1, “1010”, Y) -> (q2, vacío).
De las siguientes reglas, ¿Cuál no puede ser parte de la gramática por no cumplir los requisitos para estar en forma normal de Chomsky? VAR ->TIPO LISTA TIPO -> int LISTA -> UNAVAR , LISTA.
De las siguientes reglas, ¿Cuál puede ser parte de una gramática, por cumplir los requisitos para estar en forma normal de Chomsky? VAR ->TIPO : LISTAVARIABLES TIPO -> int LISTAVARIABLES -> UNAVAR , LISTA.
De los siguientes autómatas, ¿cuál es el más apropiado para reconocer cadenas de unos que terminen con #? (q1, “1”, X) -> (q1, X)
(q1, “#”, X) -> (q2, reconocer) (q1, “1”, X) -> (q2, 1X)
(q2, “1”, X) -> (q2, vacío)
(q2, “1”, X) -> (q2, reconocer) (q1, “1”, X) -> (q2, 1X)
(q2, “#”, X) -> (q2, reconocer).
Derivar es un proceso en el que: Se parte de las reglas y se llega a los no terminales Se parte de los no terminales y se construye reglas Se parte de los no terminales y se construye cadenas.
El autómata de pila tiene. Dos alfabetos Tres alfabetos Cuatro alfabetos.
El lenguaje de una gramática G, está representado por El conjunto de cadenas que la G puede derivar El conjunto de reglas que conforman la G El conjunto de cadenas y de reglas de la G.
El lenguaje que reconoce una gramática esta conformado Por los símbolos que puede derivar Todas las sentencias que puede derivar Todas las reglas que puede derivar.
El siguiente autómata:
(q1, “1”, X) à (q2, YX)
(q2, “0”, Y) à (q1, XY) Reconoce cadenas alternadas de 1s y 0s Reconoce cadenas alternadas de 0s y 1s Reconoce todo tipo de cadenas que tengan 1 y 0.
El símbolo inicial de la gramática Es un terminal Es un no terminal Es una regla.
En el siguiente autómata:
(q1, “1”, X) à (q2, YX)
(q2, “0”, Y) à (q1, XY) La pila guarda una X por cada 1 que reconoce La pila guarda una Y por cada 1 que reconoce La pila guarda una Y por cada 0 que reconoce.
En la definición de un autómata de pila el Símbolo Q significa Conjunto de símbolos de entrada Estado inicial Conjunto de estados.
En la siguiente gramática: S -> AbC
A -> a
C -> D
D -> b
¿en que regla se encuentra un símbolo inútil? Regla 2 Regla 3 Regla 4.
En la siguiente gramática:
BLOQUE -> INICIO RESTO
INICIO ->
RESTO -> UNAINSTRUCCIÓN FIN
FIN -> BLOQUE
BLOQUE -> UNAINSTRUCCION
UNAINSTRUCCION -> WHILE
UNAINSTRUCCION -> FOR
¿Qué grupos de reglas hay que eliminar para que la gramática quede en forma normal de chomsky? Regla 1, regla 3, regla 5, regla 6 Regla 2, regla 4, regla 5, regla 6 Regla 4, regla 5, regla 6, regla 7.
En la siguiente gramática:
VAR -> TIPO LISTA ;
TIPO -> int
TIPOS -> char
LISTA -> UNAVAR
UNAVAR -> id
MASVAR -> id, LISTA
¿en que regla se encuentra un símbolo inútil? Regla 5 Regla 6 Regla 4.
En la siguiente gramática:
VAR -> TIPO LISTA ;
TIPO -> int
UNAVAR -> vacio
LISTA -> UNAVAR, LISTA
MASVAR -> id, LISTA
Si se desea eliminar las producciones vacías, ¿Qué regla hay que eliminar? Regla 2 Regla 3 Regla 4.
En un árbol de derivación: Las hojas del árbol se representan con mayúscula Las hojas del árbol se representan con símbolos especiales Las hojas del árbol se escriben con minúscula.
En un autómata de pila el siguiente estado es determinado por La función de transición El estado inicial El alfabeto de la pila.
En un autómata de pila, la memoria la constituye la pila. Para escribir en esta pila se cuenta con un : Lenguaje de la pila Alfabeto de la pila Gramática de la pila.
En un proceso de derivación: Se aplican solo reglas que puedan generar hojas Se aplican solo reglas que generan nodos internos Se aplica la regla que sea necesaria.
La ambigüedad significa Que se pueden crear dos sentencias distintas con la misma gramática Que se pueden crear dos sentencias distintas para el mismo árbol Que se pueden crear dos árboles distintos para la misma sentencia.
La derivación de una sentencia Debe iniciar siempre por un terminal Debe iniciar siempre por un no terminal Puede iniciar por un terminal o un no terminal.
La derivación: Permite construir sentencias Permite reemplazar reglas Permite comprobar cadenas.
La diferencia entre un lenguaje independiente de contexto y un regular de contexto radica en que El independiente de contexto requiere siempre de una gramática y el regular no El independiente de contexto genera cualquier tipo de cadenas y el regular no El independiente de contexto requiere seguir reglas y el regular no.
La función de transición de un autómata de pila está formada por: Reglas Símbolos Estados.
La siguiente gramática tiene un error en una de las reglas, este error no le permite estar en forma normal de
Chomsky.
S -> A
X -> a
Y -> XY
¿En que regla está el error? Regla 1 Regla 2 Regla 3.
La siguiente gramática tiene un error en una de las reglas, este error no le permite estar en forma normal de
Chomsky.
S -> A
X -> a
Y -> XZ
¿En que regla está el error? Regla 1 Regla 2 Regla 3.
La siguiente gramática tiene un error en una de las reglas, este error no le permite estar en forma normal de
Chomsky.
S -> BC
B -> a
C -> C
¿En que regla está el error? Regla 1 Regla 2 Regla 3.
La siguiente gramática tiene un error en una de las reglas, este error no le permite estar en forma normal de
Chomsky.
S -> Y
Y -> a
Y -> SY
¿En que regla está el error? Regla 1 Regla 2 Regla 3.
La siguiente gramática tiene un error en una de las reglas, este error no le permite estar en forma normal de
Chomsky.
S ->AB
A -> aA
B -> BB
B -> b
¿En que regla está el error? Regla 1 Regla 2 Regla 3.
La siguiente regla gramatical se encuentra: S ->a En forma normal de chomsky En formato de gramática libre de contexto En las dos anteriores.
La siguiente regla gramatical se encuentra: S ->XT En forma normal de chomsky En formato de gramática libre de contexto En las dos anteriores.
La siguiente regla significa:
(q1, “0”, X) -> (q2, ZX) Que reconoce cadenas que empiezan con 1 Que la cima de la pila X se reemplaza por ZX Que la cima de la pila Z se reemplaza por X.
La siguiente regla significa:
(q1, “1”, X) -> (q2, ZX) Desde el estado q1, resta por reconocer X y 1 está en la cima de la pila Desde el estado q1, resta por reconocer 1 y X está en la cima de la pila Desde el estado q2, resta por reconocer ZX y X está en la cima de la pila.
La siguiente regla significa:
(q1, “1”, X) -> (q2, ZX) Que la cima de la pila es reemplazada por Z Que la cima de la pila es reemplazada por X Que la cima de la pila es reemplazada por ZX.
La siguiente regla significa:
(q1, “a”, X) -> (q1, vacio) Que reconoce cadenas que terminan en a Que la cima de la pila X se reemplaza por vacio Que la cima está vacia y se reemplaza por X.
La siguiente regla significa:
(q1, “a”, X) -> (q1, vacio) Que reconoce cadenas vacias Que la cima de la pila es “a” Que reconoce “a” en el estado q1.
La siguiente regla significa:
(q1, “a”, X) -> (q1, vacio) Que reconoce el símbolo “a” y escribe vacio en la cima de la pila Que reconoce el símbolo “a” cuando la pila está vacía Que reconoce “a” y coloca X en la cima de la pila.
La siguiente regla significa:
(q1, “x”, X) -> (q1, X) Que reconoce el símbolo “x” en el estado q1 Que reemplaza el símbolo “x” por “X” Que la cima de la pila se convierte en “x”.
La siguiente regla significa:
(q1, “x”, XZ) -> (q2, X) Que reconoce el símbolo “x” en el mismo estado Que reconoce el símbolo “x” cuando la pila está vacía Que la cima de la pila se reemplaza por X.
La siguiente regla significa:
(q4, “x”, X) -> (q3, vacio) Que reconoce una cadena vacía Que reemplaza la cima de la pila por vacío Que reemplaza la cima de la pila por X.
Las gramáticas tienen un elemento que permite identificar la primera regla : Se denomina primer símbolo Se denomina axioma Se denomina regla inicial.
Las reglas de un autómata de pila tienen dos partes. En la primera parte hay tres componentes, estos son: El estado, el símbolo que se reconoce y el símbolo que se lee de la pila El estado, el símbolo que se reconoce y el símbolo que se escribe en la pila Símbolo de entrada, el símbolo que se reconoce y el símbolo que se lee de la pila.
Para que el siguiente autómata reconozca cadenas alternadas de unos y ceros ¿qué cambios requiere?
(q1, “1”, X) -> (q2, YX)
(q2, “0”, Y) -> (q2, XY) El estado destino de la regla dos debe ser q1 El estado destino de la regla uno debe ser q1 El estado destino de la regla dos debe ser q3.
Para que una gramática quede en forma normal de Chomsky No debe tener más de 3 terminales No debe tener símbolos complementarios No debe tener símbolos inútiles.
Para que una gramática quede en forma normal de Chomsky, en la parte derecha debe tener: Máximo un terminal Máximo dos terminales Cualquier número de terminales.
Para que una gramática quede en forma normal de Chomsky, en la parte derecha debe tener: Solamente terminales Solamente no terminales Terminales o no terminales.
Para que una gramática quede en forma normal de Chomsky, en la parte derecha debe tener: un NO terminal dos NO terminales varios NO terminales.
Para que una gramática sea expresada en forma normal de Chomsky No debe tener más de 3 terminales en el lado derecho de cada regla No debe tener más de un terminal en el lado derecho de cada regla No puede tener más de dos símbolos en el lado izquierdo de cada regla.
Si a un autómata finito se le agrega una memoria este va a tener mayor capacidad de reconocimiento por que podrá recordar. ¿El autómata finito y la memoria con cuál de los siguientes conceptos se asocia más? Autómata finito no determinista Autómata de pila Autómata finito determinista.
Un árbol de derivación representa: De forma gráfica una sentencia de un lenguaje Un lenguaje Un conjunto de símbolos de un alfabeto.
Un autómata de pila tiene Un estado inicial Dos estados iniciales Varios estados iniciales.
Un lenguaje independiente de contexto Es más amplio que uno regular Es mas débil que uno regular Tiene la misma potencia que uno regular.
Un lenguaje independiente de contexto Reconoce más cadenas que un lenguaje regular Reconoce menos cadenas que un lenguaje regular Tiene las mismas cadenas que un lenguaje regular.
Un símbolo terminal es Un símbolo que se utiliza para derivar La hoja de un árbol de derivación El que se ubica en la parte izquierda de una regla.
Un símbolo terminal se utiliza para Construir sentencias Construir cadenas Construir reglas.
Un símbolo terminal: Es cualquier componente de la gramática Es cualquier sentencia que se forme de una gramática Es un componente de una sentencia.
Una derivación por la izquierda Construye la cadena desde la izquierda a la derecha Reemplaza el terminal (símbolo) ubicado a la derecha Reemplaza el no terminal (variable) ubicado a la derecha.
Una gramática es ambigua cuando: Existe más de dos cadenas similares en la sentencia de un lenguaje Existe más de un árbol para una sentencia de un lenguaje Tiene varias sentencias equivalentes para una expresión.
Una gramática se define formalmente con 2 componentes 3 componentes 4 componentes.
Una gramática siempre tiene en la parte izquierda de la primera regla un símbolo, este símbolo es: Un Terminal Una regla Un no terminal.
|
