7/30/2019 AUTOMOTAS
1/33
Act1: Revisin de Presaberes
Revisin del intento 1
Comenzado el: lunes, 10 de diciembre de 2012, 21:34
Completado el: lunes, 10 de diciembre de 2012, 22:02
Tiempo empleado: 28 minutos 10 segundos
Puntuacin bruta: 6/6 (100 %)
Calificacin: de un mximo de
5262 Continuar
1
Puntos: 1/1Identifique que apreciaciones son vlidas cuando se trata deanalizar la "Interseccin" y la "Unin" de dos alfabetos:Seleccione una respuesta.
a. Con los alfabetos solo podemos haceroperaciones de Unin.
b. La interseccin de dos alfabetos siempreda como resultado otro alfabeto siemptre ycuando dicha interseccin sea distinta de
vaco.
Correcto: Esdiferente el vaci alambda (cadena
vaca)c. La interseccin entre alfabetos no esposible por que se repiten elementos"Propiedad de Regularidad"
d. No hay diferencia entre la Unin y laInterseccin de Alfabetos.
La interseccin de dos alfabetos siempre da como resultado otroalfabeto siemptre y cuando dicha interseccin sea distinta de vaco.CorrectoPuntos para este envo: 1/1.La interseccin de dos alfabetos siempre da como resultado otroalfabeto siemptre y cuando dicha interseccin sea distinta de vaco.
2Puntos: 1/1
7/30/2019 AUTOMOTAS
2/33
La jerarqua de Chomsky tiene como nico objetivo:Seleccione una respuesta.
a. Clasificar los diferentes tiposde alfabetos que definen un
lenguaje determinado.b. Clasificar de forma jerrquicalos tipos de Autmatas (Finitos oInfinitos) de acuerdo a lasgramticas y lenguajes quereconocen.
c. Ordenar y clasificar losdiferentes tipos de gramticas
que generan lenguajes.
Correcto: Clasicacionesbasadas en la forma de lagramtica, ms que en la
naturaleza del lenguaje quegeneran.
d. Clasificar de forma ordenadalos diferentes modelos decomputacin de acuerdo a lasgramticas y lenguajes queexisten.
La jerarqua de Chomsky es una clasificacin jerrquica de distintostipos de gramticas formales que generan lenguajes formales. Esta
jerarqua fue descrita por Noam Chomsky en 1956.CorrectoPuntos para este envo: 1/1.La jerarqua de Chomsky es una clasificacin jerrquica de distintostipos de gramticas formales que generan lenguajes formales. Esta
jerarqua fue descrita por Noam Chomsky en 1956.
3
Puntos: 1/1Teniendo en cuenta que podemos definir un Autmata como unamquina conceptual o terica para el reconocimiento de patrones,entonces los siguientes componentes: Analizador Lxico, AnalizadorSintctico y Generador de Cdigo corresponderan a una aplicacinde un Autmata en el la implementacin de:Seleccione una respuesta.
7/30/2019 AUTOMOTAS
3/33
a.
Compiladores
Correcto: Un autmata reconocedor de eselenguaje, funciona de tal forma que cuandoreciba a su entrada una determinada cadena desmbolos indica si dicha cadena pertenece o no
al lenguaje. Tambin se mostrar como existeun tipo de autmata para reconocer cada unode los tipos de lenguajes generados por lascorrespondientes gramticas.
b. Aplicacionesde Computador
c. Lenguajes deProgramacin
d.
Procesadoresde texto
Un autmata reconocedor de ese lenguaje, funciona de tal formaque cuando reciba a su entrada una determinada cadena desmbolos indica si dicha cadena pertenece o no al lenguaje.Tambin se mostrar como existe un tipo de autmata parareconocer cada uno de los tipos de lenguajes generados por lascorrespondientes gramticas.Correcto
Puntos para este envo: 1/1.La palabra autmata evoca algo que pretende imitar las funcionespropias de los seres vivos, especialmente relacionadas con elmovimiento, por ejemplo el tpico robot antropomorfo. En el campode los Traductores, Procesadores, Compiladores e Intrpretes, lofundamental no es la simulacin del movimiento, sino la simulacinde procesos para tratar informacin.
4
Puntos: 1/1De un Lenguaje Libre de Contexto podemos afirmar que es:Seleccione una respuesta.
a. Es el Algoritmo que nosindica el lenguaje de lagramtica
7/30/2019 AUTOMOTAS
4/33
b. Es un Lenguaje que esgenerado por unagramtica libre de contexto
Correcto: (gramticas libres delcontexto) generan los lenguajesindependientes del contexto.
c. Es lo mismo que decir
un Autmata Libre deContexto
d. Es un lenguaje regular
(gramticas libres del contexto) generan los lenguajesindependientes del contexto.CorrectoPuntos para este envo: 1/1.Consideramos entonces los lenguajes libres (independientes) delcontexto, y las gramticas libres del contexto y los autmatas con
pila, como forma de caracterizarlos y manejarlos. Los distintoslenguajes formales que se pueden construir sobre un alfabetoconcreto pueden clasificarse en clases cada vez ms amplias queincluyen como subconjunto a las anteriores, de acuerdo con la
jerarqua establecida por Chomsky en los aos 50.
5Puntos: 1/1Cules de los siguientes elementos son necesarios para conocer el
estado de un Autmata en un momento dado.Seleccione al menos una respuesta.
a. Smbolo deEntrada
Correcto: El estado de un autmata es toda lainformacin necesaria en un momento dado,para poder deducir, dado un smbolo de entradaen ese momento, cual ser el smbolo de salida
b. Estado FinitoIncorrecto. El estado de un autmata es toda lainformacin necesaria en un momento dado
c. Cadenarechazada
Incorrecto: Las cadenas rechazadas no puedendeterminar el estado actual de un Autmata.
d. Lenguaje
e. Smbolo desalida
Correcto: El estado de un autmata es toda lainformacin necesaria en un momento dado,para poder deducir, dado un smbolo de entrada
7/30/2019 AUTOMOTAS
5/33
en ese momento, cual ser el smbolo de salida
f. Cadenaaceptada
Incorrecto: Las cadenas o palabras nodeterminan el estado actual del autmata.
g. Lenguaje que
reconoce elautmata.
Incorrecto: El lenguaje que reconoce el
autmata es independiente del nmero deestados.
h. Alfabeto
Se define configuracin de un autmata a su situacin en uninstante. Se define movimiento de un autmata como el transitoentre dos configuraciones. Si un autmata se encuentra en unestado determinado, recibe un smbolo tambin determinado,producir un smbolo de salida y efectuar un cambio o transicin aotro estado (tambin puede quedarse en el mismo estado).
CorrectoPuntos para este envo: 1/1.Conocer el estado de un autmata, es lo mismo que conocer toda lahistoria de smbolos de entrada, as como el estado inicial, estadoen que se encontraba el autmata al recibir el primero de lossmbolos de entrada. El autmata tendr un determinado nmero deestados (pudiendo ser infinitos), y se encontrar en uno u otrosegn sea la historia de smbolos que le han llegado.
6Puntos: 1/1
Asocie correctamente la estructura de la clase de lenguajes y lasgramticas que los pueden generar: "Jerarqua de Chomsky"
Se denominan dependientes del contexto.Los lenguajes aceptados por estasgramticas son los lenguajes dependientesdel contexto
Las gramticas de tipo 1
Se denominan regulares o de estado nito. Loslenguajes aceptados por estas gramticas sedenominan conjuntos regulares.
Las gramticas de tipo 3
As como los lenguajes generados, se llamanindependientes del contexto.
Las gramticas de tipo 2
CorrectoPuntos para este envo: 1/1.
7/30/2019 AUTOMOTAS
6/33
N. Chomsky (1956) propone tres modelos para la descripcin delenguajes, que son la base de su futura jerarqua de los tipos delenguajes, que ayud tambin en el desarrollo de los lenguajes deprogramacin.
5262
Act 3: Reconocimiento Unidad No. 1
Revisin del intento 1
Comenzado el: domingo, 2 de diciembre de 2012, 11:40
Completado el: domingo, 2 de diciembre de 2012, 11:58
Tiempo empleado: 18 minutos 5 segundos
Puntuacin bruta: 5/6 (83 %)
Calificacin: de un mximo de
Comentario - Correcto: Contest la totalidad de las preguntas.
5265 Continuar
1Puntos: 1/1
Asocie correctamente los siguientes conceptos con referencia al
tipod elenguajes que pueden implementar las mquinas(Autmatas).
Gramticas Independientes del Contexto Autmatas de Pila
Gramticas Generales Mquinas de Turing
En Autmatas cuando tenemos lenguajes muysencillos
Regularidad
Lenguajes (Expresiones Regulares) Autmatas Finitos
Correcto
Puntos para este envo: 1/1.Los Lenguajes ms sencillos son los considerados lenguajesregulares, es decir, los que se pueden generar a partir de lenguajesde un elemento con la aplicacin de ciertas operaciones estandarrealizadas un nmero finito de veces. Estos son pues los lenguajesque pueden reconocer los dispositivos llamados Autmatas finitos
7/30/2019 AUTOMOTAS
7/33
(AF) que son mquinas de cmputo con memoria muy restringida.En esta unidad se considera como segundo aspecto la idea de queun lenguaje no sea regular, ademas de proporcionar un modelosencillo de computacin que se puede generalizar en las unidades
siguientes.
2Puntos: 1/1El nombre determinista viene de:Seleccione una respuesta.
a. La cantidad deestados iniciales y
sentencias que lacomponen
b. La cantidad deestados finalesque la componen
c. El tipo delenguaje quereconoce
d. La forma enque est definidala funcin detransicin
Correcto:El nombre determinista viene de la
forma en que est definida la funcin detransicin: si en un instante t la mquina esten el estado q y lee el smbolo a entonces, enel instante siguiente t + 1 la mquina cambiade estado y sabemos con seguridad cual es elestado al que cambia, que es precisamente(q, a).
El diagrama de transicin de un AFD tiene por cada nodo un soloarco etiquetado con cada uno de los smbolos del alfabeto. Algunos
autores consideran que la funcin de transicin puede ser parcial,es decir, no estar definida para algn (q, a). En ese caso se diceque el AFD es incompleto, y en el diagrama de trancisin faltanentonces los arcos correspondientes a los casos no definidos de lafuncin de transicin.CorrectoPuntos para este envo: 1/1.
7/30/2019 AUTOMOTAS
8/33
El diagrama de transicin de un AFD tiene por cada nodo un soloarco etiquetado con cada uno de los smbolos del alfabeto. Algunosautores consideran que la funcin de transicin puede ser parcial,es decir, no estar definida para algn (q, a). En ese caso se dice
que el AFD es incompleto, y en el diagrama de trancisin faltanentonces los arcos correspondientes a los casos no definidos de lafuncin de transicin.
3Puntos: 1/1
Identifique la forma como se puede caracterizar, identificar o clarificar un lenguaje.
Seleccione una respuesta.a. Mediante el uso dealfabetos definidos ycortos que no conviertanal lenguaje complejo.(Ejemplo el sistemabinario)
b. Se puede caracterizarun Lenguaje, mediantelas reglas de unagramtica adecuada.
Esta es la respuesta correcta: Losintentos de formalizar los lenguajes,
lleva a la construccin de gramticas,como una forma de describir estoslenguajes, utilizando para ello reglas deproduccin para construir las frases dellenguaje
c. Mediante las reglassemnticas rgidas yconcretas bien definidas
d. Mediante las reglas
sintcticas rgidas yconcretas bin definidas.
Los intentos de formalizar los lenguajes, lleva a la construccin degramticas, como una forma de describir estos lenguajes, utilizandopara ello reglas de produccin para construir las frases del lenguajeCorrecto
7/30/2019 AUTOMOTAS
9/33
Puntos para este envo: 1/1.Un Lenguaje normal o natural, como por ejemplo el lenguajeespaol u ingls, son la clase de lenguajes que han evolucionadocon el paso del tiempo y tienen por fin la comunicacin humana.
Este tipo de lenguajes estn en constante evolucin y sus reglasgramaticales solo pueden ser explicadas y no determinadas encuanto a la estructura del lenguaje.
4Puntos: 1/1
Los lenguajes se pueden clasificar segn el tipo de dispositivos de aceptacin y generacin
que existen para ellos. Con respecto a esto, asocie correctamente los siguientes textos:
Losmecanismosdeaceptacinde loslenguajesregulares yde loslenguajes
libres decontextoforman labase para
el diseo de los analizadores lxicos y sintcticos de los compiladores.
Alfabeto Conjunto finito no vaco de elementos.
Lenguaje Conjunto de palabras o sentencias formadas sobre un alfabeto.
Losdispositivosdegeneracinde loslenguajesregulares yde loslenguajes
la sintaxis de los lenguajes de programacin.
7/30/2019 AUTOMOTAS
10/33
libres decontexto,sonampliament
e usadoscomomodelosparaexpresar la
CorrectoPuntos para este envo: 1/1.Informalmente, el trmino lenguaje formal se utiliza en muchoscontextos (en las ciencias, en derecho, etc.) para referirse a unmodo de expresin ms cuidadoso y preciso que el habla cotidiana.Hasta finales de la dcada de 1990, el consenso general era que unlenguaje formal, era en cierto modo la versin lmite de este usoantes mencionado: un lenguaje tan formalizado que poda ser usadoen forma escrita para describir mtodos computacionales. Sinembargo, hoy en da, el punto de vista de que la naturaleza esencialde los lenguajes naturales (sin importar su grado de formalidad enel sentido informal antes descrito) difiere de manera importante deaquella de los verdaderos lenguajes formales, gana cada vez msadeptos.
5Puntos: 0/1
1. Se denomina cadena, palabra o frase a una secuencia finita de smbolos de un alfabeto
. Estas cadenas son denotadas como w.
Dado el siguiente autmata finito determinstico (AFD) A = (Q, , f, q0, F) donde:
Q es un conjunto de estados.
es el alfabeto de entrada
f: Q X Q es la funcin (total) de transicin.
q0 pertenece Q es el estado inicial.
7/30/2019 AUTOMOTAS
11/33
F incluye Q es el conjunto de estados finales.
Y que para el ejercicio = {a,b} Q ={ q0, q1} F = {q1} se representamediante el siguiente diagrama de Moore:
El conjunto de palabras aceptadas por este autmata son:
Seleccione una respuesta.
a. {w a | w {a,b}* }
b. {w a | w {a,b} potencia 2 }
c. Todas las palabras que terminan en dos as Incorrecto
d. Todas las palabras que terminan en a y que estnprecedidas por una b
Tengase en cuenta la operacin estrella que es la que estdeterminando el tipo de cadenas vlidas que acepta el autmata.IncorrectoPuntos para este envo: 0/1.El conjunto de palabras aceptadas por este autmata son lapalabras que terminan en a.
6Puntos: 1/1
7/30/2019 AUTOMOTAS
12/33
Identifique la operacin bsica y que es correcta para un Autmata .
Seleccione una respuesta.
a. El autmata recibe los smbolos de
entrada en orden aleatorio o endiferentes estados y la funcin de esteautmata (Mquina) es ordenarlos einterpretarlos.
b. El smbolo de salida que en uninstante determinado produce unautmata, no slo depende del ltimosmbolo recibido a la entrada, sino detoda la secuencia o cadena, que ha
recibido hasta ese instante.
Esta es la respuestacorrecta: Un autmataproduce entradas ysalidas ordenadas quedependen del estado en
que se encuentre.c. El autmata no es una simulacin.No es una mquina.
d. La informacin que codifica elautmata es convertida a un sistemade dos dgitos (entrada y salida) esdecir (1 y 0), Sistema binario
Para comprender el significado de Autmata, tendremos en cuentael trmino mquina, que evoca algo hecho en metal, usualmente
ruidoso y grasoso, que ejecuta tareas repetitivas que requieren demucha fuerza o velocidad o precisin.CorrectoPuntos para este envo: 1/1.Desde el punto de vista intuitivo, podemos ver un autmata finitocomo una caja negra de control, que va leyendo smbolos de unacadena escrita en una cinta, que se puede considerar ilimitada porla derecha. Existe una cabeza de lectura que en cada momento estsituada en una casilla de la cinta. Inicialmente, esta se sita en la
casilla de ms a la izquierda
7/30/2019 AUTOMOTAS
13/33
Act 4: Leccin Evaluativa Unidad No.1
Revisin del intento 1
Comenzado el: domingo, 2 de diciembre de 2012, 12:21
Completado el: domingo, 2 de diciembre de 2012, 13:00
Tiempo empleado: 39 minutos 5 segundos
Puntuacin bruta: 4.57/10 (46 %)
Calificacin: de un mximo de
Comentario - Correcto
5266 Continuar
1Puntos: 0/1
Acerca de la cadena vaca lambda se puede afirmar que:
Seleccione una respuesta.
a. Es un palndromo
b. Es un Autmata finito (AF)
c. Es un smbolo y no es parte de un lenguaje
d. No es una cadena sino un smbolo Incorrecto.Palndromos (palabras que se leen igual al derecho y al revs, como
ANITALAVALATINA). labada puede ser repetitivo al igual que comopor ejemplo la cadena {aa}IncorrectoPuntos para este envo: 0/1.Palndromos (palabras que se leen igual al derecho y al revs, como
ANITALAVALATINA). labada puede ser repetitivo al igual que comopor ejemplo la cadena {aa}
2Puntos: 0.5/1Sea el autmata A = (, Q, f, q1, F) donde
={a,b},Q ={q1, q2, q3, q4},F={q4}y la funcin f vienen dada por la siguientetabla:
7/30/2019 AUTOMOTAS
14/33
Determine qu aspectos son vlidos para el autmata.
Seleccione al menos una respuesta.
a. Es un Autmata Finito Determinstico(AFD)
b. Es un Autmata Finito Determinstico conlambda - transiciones
c. El lenguaje reconocido por el autmataes: a (b* | a* ) ba*
Correcto. Esta ERes vlida
d. El lenguaje reconocido por el autmataes: a (b*b | a*b) a*
Parcialmente correctoPuntos para este envo: 0.5/1.Es un AFND. El lenguaje que reconoce es : a (b*b | a*b) a* otambin a (b* | a* ) ba* para efectos de mejor comprensin, se debeescojer una cadena vlida y compararla con la ER.
3Puntos: 0.67/1Los autmatas y su definicin se pueden representar mediante :
Seleccione al menos una respuesta.
a. Tabla de transicionesCorrecto: Se pueden identificarestados, transiciones y desde all sepuede identificar las cadenas vlidas.
b. Diagramas de Moore Correcto: Los diagramas de Moore son
7/30/2019 AUTOMOTAS
15/33
otra forma de representar las funcionesde transicin y salida de un autmata.
c. Descripcinmatemtica de la funcin
de transicind. El conjunto de tablasrepresentativas
Parcialmente correctoPuntos para este envo: 0.67/1.La palabra autmata evoca algo que pretende imitar las funcionespropias de los seres vivos, especialmente relacionadas con elmovimiento. Se pueden represnerar o definir mediante las tablas detransicin, Diagramas de Moore, La funcin de transicin.
4Puntos: 0/1
Dado el siguiente Autmata Finito cuyo diagrama de transicin corresponde al de la
siguiente figura, determine cuales afirmaciones son vlidas cuando se analiza laejecucin del autmata.
Seleccione una respuesta.
a. El conjunto de cadenas que escapaz de reconocer este autmata es.{, b, bb, bbb, bbbb, }
b. El conjunto de cadenas que escapaz de reconocer este autmata es.{b}
Incorrecto: Tngase encuenta la stransicioneslambda.
7/30/2019 AUTOMOTAS
16/33
c. El conjunto de cadenas que escapaz de reconocer este autmata es{b, bb, bbb}
d. El conjunto de cadenas que es
capaz de reconocer este autmata es.{b, bb, bbb, bbbb, }
Las transiciones lambda son vlidas y se deben tener en cuenta alanlisis del lenguaje aceptado por el autmata.IncorrectoPuntos para este envo: 0/1.Se evala la cadena hasta llegar al estado de aceptacin o final q5.El conjunto de cadenas que es capaz de aceptar este autmata es{b,bb.bbb}
5Puntos: 1/1
Acerca de la Equivalencia de AFD Y AFN es vlido afirmar.Seleccione una respuesta.
a. Los autmatas finitos determinsticos (AFD) son unsubconjunto propio de los no determinsticos (AFN)
Correcto.
b. Para covertir u AFD a u AFND, el AFD debe tener
menos estados que el AFNDc. Todo Autmata por defecto es Determinstico.
d. Todo Autmata por defecto es No determinstico
Los autmatas finitos determinsticos (AFD) son un subconjuntopropio de los no determinsticos (AFN), lo que quiere decir que todo
AFD es un AFN. Podra entonces pensarse que los AFN son mspoderosos que los AFD, en el sentido de que habra algunoslenguajes aceptados por algn AFN para los cuales no habraningn AFD que los acepte. Sin embargo, en realidad no sucede
as.CorrectoPuntos para este envo: 1/1.Los autmatas finitos determinsticos (AFD) son un subconjuntopropio de los no determinsticos (AFN), lo que quiere decir que todo
AFD es un AFN. Podra entonces pensarse que los AFN son mspoderosos que los AFD, en el sentido de que habra algunos
7/30/2019 AUTOMOTAS
17/33
lenguajes aceptados por algn AFN para los cuales no habraningn AFD que los acepte. Sin embargo, en realidad no sucedeas.
6Puntos: 1/1
Asocie los trminos correctamente:
Incluyen a los Libres de Contexto (ypor lo tanto a los LenguajesRegulares).
Lenguajes Recursivamente Enumerables
Es la clase ms pequena, e incluyea los lenguajes ms simples
Lenguajes Regulares
Conjunto finito Alfabeto Incluyen a los Lenguajes Regulares Lenguajes Libres de Contexto
Conjunto de palabras (cadenas decaracteres) de longitud finitaformadas a partir de un alfabeto(conjunto de caracteres) finito.
Lenguaje Formal.
Jerarqua de Lenguajes Chomsky
CorrectoPuntos para este envo: 1/1.
Llamamos clase de lenguajes a conjuntos de lenguajes quecomparten una cierta propiedad dada. Esta nocin es muyabstracta, pues ya los lenguajes son en s mismos conjuntos desecuencias de smbolos, y las clases de lenguajes son entoncesconjuntos de conjuntos de secuencias de smbolos.
7Puntos: 1/1
Sea el Autmata Finito (AF)A= (, Q, f. q1, F) donde = {0,1} , Q ={q1, q2, q3, q4 },F={q2}y definimos la funcin de transicin fpor la tabla siguiente:
7/30/2019 AUTOMOTAS
18/33
Indique cul es lenguaje generado por el autmata:
Seleccione una respuesta.
a. 1*(1)b. 1( 1)(0)*
c. 1(01) *Correcto: La expresin regular genera las cadenas queinician con 1 y que luego pueden o no tener un 0 o un 1.
d.0(010)*
La expresin regular genera las cadenas que inician con 1 y que
luego pueden o no tener un 0 o un 1 .CorrectoPuntos para este envo: 1/1.La tabla de transicin tambin es una forma de describir un
Autmata. Con ella se puede identificar su ER. La expresin regulargenera las cadenas que inician con 1 y que luego pueden o no tenerun 0 o un 1 .
8Puntos: 0.4/1
Defina los siguientes conceptos: smbolo, alfabeto, palabra, lenguaje y gramatica.
Secuencias o cadenas de caracteres Palabras
Una representacin distinguible de cualquier informacin Lenguaje
7/30/2019 AUTOMOTAS
19/33
Conjunto de reglas para formar correctamente las frasesde un lenguaje.
Gramtica
Un conjunto de palabras Elegir...
Un conjunto no vaco de smbolos. Smbolo
Parcialmente correctoPuntos para este envo: 0.4/1.La nocin ms primitiva es la de smbolo, que es simplemente unarepresentacin distinguible de cualquier informacin. Los smbolospueden ser cualesquiera, como w, 9, #, etc., Un smbolo es unaentidad indivisible.
9Puntos: 0/1En un autmata Finito Determinista (AFD), Es vlido afirmar que :Seleccione una respuesta.
a. El nombre determinista viene de laforma en que est definida la funcin detransicin: si en un instante t la mquinaest en el estado q y lee el smbolo aentonces, en el instante siguiente t + 1 lamquina cambia de estado y sabemos con
seguridad cual es el estado al que cambia,que es precisamente (q, a).
Respuesta Correcta:La funcin detransicin define quesea determinado ono.
b. A diferencia de los AF (AutmatasFinitos), los Autmatas FinitosDeterminsticos Por ser AFD, este no debeser inicializado con ningn smbolo deentrada
c. Todo autmata finito determinista de nestados, cuyo alfabeto E contiene m
smbolos debe tener m x n transiciones.d. A diferencia de los AF (AutmatasFinitos), los Autmatas FinitosDeterminsticos Por ser AFD, no tienenningn ciclo de ejecucin. Solo leen un datode entrada.
7/30/2019 AUTOMOTAS
20/33
Una extensin a los autmatas finitos deterministas es la de permitirque de cada nodo del diagrama de estados salga un nmero deflechas mayor o menor que As, se puede permitir que falte la flechacorrespondiente a alguno de los smbolos del alfabeto, o bien que
haya varias flechas que salgan de un solo nodo con la mismaetiqueta. Inclusive se permite que las transiciones tengan comoetiqueta palabras de varias letras o hasta la palabra vaca. A estosautmatas finitos se les llama no Determinsticos o no deterministas(abreviado AFND),IncorrectoPuntos para este envo: 0/1.El nombre determinista viene de la forma en que est definida lafuncin de transicin: si en un instante t la mquina est en elestado q y lee el smbolo a entonces, en el instante siguiente t + 1 lamquina cambia de estado y sabemos con seguridad cual es elestado al que cambia, que es precisamente (q, a).
10Puntos: 0/1
Indique cul de las siguientes afirmaciones se apropia a los conceptos de los AutmatasFinitos:
Seleccione una respuesta.
a. Los autmatas finitostienen un nmero finito deestados.
b. Ninguna de lasafirmaciones anteriores escierta
Tengase en cuenta el trmino"finito" cuando se describenmquinas computacionales.
c. Los autmatas finitos slo
pueden aceptar lenguajesfinitos.
d. Las mquinas de Turing ylos autmatas de pila sonautmatas finitos
Una mquina de estados finitos M es un quntuplo claramentedefiniendo sus elementos, entre ellos que estados tiene.
7/30/2019 AUTOMOTAS
21/33
IncorrectoPuntos para este envo: 0/1.
Al describir una mquina de estados finitos en particular, debemosincluir las informaciones que varan de un autmata a otro; es decir,
no tiene sentido incluir descripciones generales aplicables a todoautmata. Estas informaciones son exactamente las que aparecenen un diagrama de estados y transiciones.
5266
Act 5: Quiz 1 - Unidad No. 1
Revisin del intento 1
Comenzado el: domingo, 2 de diciembre de 2012, 12:00
Completado el: domingo, 2 de diciembre de 2012, 12:20
Tiempo empleado: 20 minutos 13 segundos
Puntuacin bruta: 10/15 (67 %)
Calificacin: de un mximo de
Comentario - Contesto parcialmente
5267 Continuar
1Puntos: 1Uno de los principales factores determinantes en la revolucin en elmbito de la ciencia, la tcnica y la cultura de nuestros das es eldesarrollo de la Informtica PORQUE Un lenguaje natural como elingls o el espaol son la clase de lenguajes que han evoucionadocon el paso del tiempo y tienen por fin la comunicacin humana.Seleccione una respuesta.
a. La Afirmacin y la Razn son VERDADERAS yla Razn es una explicacin CORRECTA de la
Afirmacin
b. La Afirmacin es VERDADERA, pero la Raznes una proposicin FALSA
c. La Afirmacin es FALSA, pero la Razn es una
7/30/2019 AUTOMOTAS
22/33
proposicin VERDADERA
d. La Afirmacin y la Razn son VERDADERASpero la Razn NO es una explicacin CORRECTAde la Afirmacin
RespuestaCorrecta
CorrectoPuntos para este envo: 1/1.
2Puntos: 1Un ejemplo de Lenguaje es el conjunto de palndromos (cadenasque se leen igual hacia adelante, que hacia atrs). Para el caso delalfabeto { 0, 1} Es vlido afirmar: (Seleccione dos respuestas).
Tenga en cuenta que el smbolo lambda (usado en autmatas),http://es.wikipedia.org/wiki/LambdaSeleccione al menos una respuesta.
a. Pueden ser cadenasvlidas como: {lambda, 0, 1.00, 11, 010, 0110, 000000,101101, 10001}
Correcto: Este lenguaje {0,1} tienecadenas infinitas (muchisimas sepueden combinar comopalindromos que se lean iagual alderecho y al reves).
b. Este Lenguaje tienecadenas finitas
c. Las cadenas vlidas paraese alfabeto obedece a susseis posibles combinaciones:{0, 1, 01, 10, 00, 11}
d. Este Lenguaje tienecadenas infinitas
Correcto: Este lenguaje {0,1} tienecadenas infinitas (muchisimas sepueden combinar como
palindromos que se lean iagual alderecho y al reves).
CorrectoPuntos para este envo: 1/1.Los lenguajes regulares se llaman as porque sus palabrascontienen regularidades o repeticiones de los mismoscomponentes, como por ejemplo en el lenguaje L1 siguiente: L1 =
7/30/2019 AUTOMOTAS
23/33
{ab, abab, ababab, abababab, . . .} En este ejemplo se aprecia quelas palabras de L1 son simplemente repeticiones de ab cualquiernmero de veces. Aqu la regularidad consiste en que las palabrascontienen ab algn nmero de veces.
3Puntos: 1Indique cual de las siguientes afirmaciones aplica correctamente alas caractersticas o definicones de un AF.Seleccione una respuesta.
a. Un automata finito no determinista es una representacionabreviada de un automata finito determinista.
b. Ninguna de las afirmaciones anteriores es ciertac. En un diagrama completo que represente a un automata finitodeterminista, de cada estado sale un arco por simbolo y solouno.
d. Los automatas finitos no deterministas son mas potentes quelos automatas finitos deterministas
IncorrectoPuntos para este envo: 0/1.
4Puntos: 1Una de las siguientes afirmaciones NO aplica a los lenguajes quereconocen un autmata. IdentifquelaSeleccione una respuesta.
a. Un automata finito determinista utilizado como reconocedor delenguajes con al menos una cadena necesariamente tiene quetener al menos un estado de aceptacion.
b. Dada una gramatica regular G, siempre existe un automatafinito M tal que L(G) = L(M) y M tiene un unico estado deaceptacion.
c. Un automata reconoce una cadena cuando alcanza un estadode aceptacion durante su lectura
d. Un automata finito determinista M reconoce un lenguaje L(M)
7/30/2019 AUTOMOTAS
24/33
si acepta exclusivamente la coleccion de cadenas de dicholenguaje.
IncorrectoPuntos para este envo: 0/1.
5Puntos: 1Los palindromos (palabras capicuas) del idioma castellano, talescomo "a", "y", "dad", "oso", "erre", etc., constituyen un:Seleccione una respuesta.
a. Lenguaje estructurado por frases (en sentido estricto)
b. Es una maquina de turing.
c. Lenguaje regulard. Lenguaje independiente del contexto (en sentido estricto)
CorrectoPuntos para este envo: 1/1.
6Puntos: 1Los Automatas finitos no Deterministicos tienen las caracteristicas
de:Seleccione al menos una respuesta.
a. Permitir que de cada nodo del diagrama de estados salga unnumero de flechas mayor o menor.
b. No permitir que cada nodo del diagrama de estados salga unnumero de flechas mayor o menor.
c. Las transiciones no tengan como etiqueta palabras de variasletras o hasta la palabra vacia.
d. Las transiciones tengan como etiqueta palabras de variasletras o hasta la palabra vacia.
CorrectoPuntos para este envo: 1/1.
7
7/30/2019 AUTOMOTAS
25/33
Puntos: 1Un Autmata Determinstico de estados finitos (DFA), M, es unaquntupla: (Q, , qi, F, ), donde:
Q es un conjunto finito de estados. es un alfabeto finito. qi Q es el estado inicial. F Q son los estados finales. : (Q ) Q es la funcin de transicin de estados.
La condicin de ser Determinstico es debido a que:
Seleccione al menos una respuesta.
a. El autmata comienzaen el estado inicial y leeuna secuencia de smbolos(smbolo por smbolo hastaque se acabe lasecuencia).
b. Las transacciones estndescritas por una funcintotal.
Esto corresponde a la definicin deAutmatas Determinsiticos (DFA).Estos autmatas se denominan
determinsticos ya que en cadaestado su comportamiento es fijo. Esdecir, dado el estado y el smbolo enla cinta de entrada hay un nicoestado al cual puede pasar. . Todaslos items son verdaderas.
c. En cada instante lee unsmbolo y dependiendo
del smbolo y del estado sen el que se encuentra,cambia al estado dado porla funcin de transicin:(s, )
Esto corresponde a la definicin deAutmatas Determinsiticos (DFA).Estos autmatas se denominan
determinsticos ya que en cadaestado su comportamiento es fijo. Esdecir, dado el estado y el smbolo enla cinta de entrada hay un nicoestado al cual puede pasar. . Todaslos items son verdaderas.
d. Hay un nico estado
7/30/2019 AUTOMOTAS
26/33
inicial.
Parcialmente correctoPuntos para este envo: 0.5/1.El nombre determinista viene de la forma en que est definida la
funcin de transicin: si en un instante t la mquina est en elestado q y lee el smbolo a entonces, en el instante siguiente t + 1 lamquina cambia de estado y sabemos con seguridad cual es elestado al que cambia, que es precisamente (q, a).
8Puntos: 1En un contexto general un Lenguaje lo podemos definir como:Seleccione una respuesta.
a. Significado de las cadenas que lo componen
b. Conjunto de instrucciones que indican accionesa realizar
c. Estudio de las reglas y principios que regulansu uso
d. Un Sistema de Smbolos Convencionales,hablados o escritos con el que nos comunicamos
RespuestaCorrecta
Correcto
Puntos para este envo: 1/1.
9Puntos: 1Indicar cul es el tipo de autmata ms sencillo (menos potente)capaz de reconocer el lenguaje {xnymzn | n>=25, m>=50}.Seleccione una respuesta.
a. Un autmata de pila no determinista Incorrecto
b. Un autmata de pila determinista
c. Una mquina de Turing.
d. Un autmata finito
IncorrectoPuntos para este envo: 0/1.
7/30/2019 AUTOMOTAS
27/33
10Puntos: 1Para el siguiente Autmata Finito denotado como: A2 = (E. Q, f, q1 ,
F) donde E = {0,1}, F = {q2 } y Q = {q1, q2 , q3 , q4 }, identifiquecorrectamente el Lenguaje que genera y la expresin regular:
OPCUINES DE RESPUESTA:
OPCION A. L = (A2) = {0, 001, 01111, } = { 1(10)n/n 0} La
expresin regular es: 0(01) *OPCION B. L = (A2 ) = {1, 101, 10101, } = { 1(01)
n/n 0} La
expresin regular es: 1(01) *OPCION C. L = (A 2) = {0, 111, 11100, } = { 1(10)
n/n = 0} La
expresin regular es: 1(01) +OPCION D. L = (A
2) = {0, 001, 00100, } = { 1(01)
n/n 0} La
expresin regular es: 0(01) *
Seleccione una respuesta.
a.OPCION(A)
7/30/2019 AUTOMOTAS
28/33
b.OPCION(D)
c.
OPCION(C)
d.OPCION(B)
Correcto: El lenguaje genrado se obtiene partiendodel estado inicial y recorriendo todos los caminosposibles para alcanzar el estado final.
CorrectoPuntos para este envo: 1/1.La notacin de conjuntos nos permite describir los lenguajesregulares, pero se utiliza una notacin en que las representaciones
de los lenguajes son simplemente texto (cadenas de caracteres).As las representaciones de los lenguajes regulares sonsimplemente palabras de un lenguaje (el de las representacionescorrectamente formadas). Con estas ideas se va a definir unlenguaje, el de las expresiones regulares, en que cada palabra va adenotar un lenguaje regular.
11Puntos: 1
Sea el vocabulario {1,2,3}, la expresin regular (1|2)* 3 indica elconjunto de todas las cadenas formadas con los smbolos 1,2 y 3 .Cules sentencias o cadenas son vlidas :Seleccione al menos una respuesta.
a.121211223
Correcto: Pueden formarse cadenas con lossmbolos 1 y 2, sucedndose cualquir nmero deveces ( y en cualquir rden) y siempre terminandola cadena en el smbolo 3
b. 132211
c. 221113
Correcto: Pueden formarse cadenas con lossmbolos 1 y 2, sucedndose cualquir nmero deveces ( y en cualquir rden) y siempre terminandola cadena en el smbolo 3
d. 2213311
Correcto
7/30/2019 AUTOMOTAS
29/33
Puntos para este envo: 1/1.Un posible alfabeto sera, digamos, {a, b}, y una cadena cualquierasobre este alfabeto sera, por ejemplo, ababba. Un lenguaje sobreeste alfabeto, que incluyera esta cadena, sera: el conjunto de todas
las cadenas que contienen el mismo nmero de smbolos a que b.
12Puntos: 1Las cadenas no nulas, en un alfabeto se crean por: (seleccionesdos opciones de respuesta).Seleccione al menos una respuesta.
a. En un alfabeto no
existen cadenas nonulas
b. Longitud mnima delalfabeto unida alnmero mximo decombinaciones.
c. Interseccin de losvalores de lambda
Correcto: Las cadenas no nulas, en unalfabeto se crean por concatenacion decadenas sencillas, las de longitud 1.
Tambien es posible ver la concatenacincomo una operacin en lenguajes, demodo que se podran considerar loslenguajes obtenidos por concatenacinde lenguajes sencillos de la forma {a},donde a PERTENECE A
d. Concatenacin decadenas sencillas, lasde longitud 1.
Incorrecto: Las cadenas no nulas, en unalfabeto se crean por concatenacion decadenas sencillas, las de longitud 1.
Tambien es posible ver la concatenacincomo una operacin en lenguajes, demodo que se podran considerar loslenguajes obtenidos por concatenacinde lenguajes sencillos de la forma {a},donde a PERTENECE A
Parcialmente correcto
7/30/2019 AUTOMOTAS
30/33
Puntos para este envo: 0.5/1.Las cadenas no nulas, en un alfabeto se crean por concatenacionde cadenas sencillas, las de longitud 1.
13Puntos: 13. Partiendo de la definicin de que un Autmata FinitoDeterminstico (AFD) est dado por la quntupla: A = (Q, , f, q0 , F)donde: Q es un conjunto de estados. es el alfabeto de entrada f: Q X Q es la funcin (total) de transicin. q0 que pertenece a Q es el estado inicial.
Y que para el ejercicio, el autmata acepta las cadenas (01)n
1) :,
A = ({q0 , q1 , q2 , q3 } , {0,1} , f , q0 , { q2 })
Representado mediante el grafo:
La tabla de transicin correspondiente es:
7/30/2019 AUTOMOTAS
31/33
Seleccione una respuesta.
a. TABLA DETRANSICION C
b. TABLA DETRANSICION B
Correcto: La transicin correcta es la B. estidentificado de forma correcta el estado inicial,el estado final con un * y las transiciones (conlos elementos de entrada) acordes al grafo.Opcin B.
c. TABLA DETRANSICION A
d. TABLA DETRANSICION D
CorrectoPuntos para este envo: 1/1.El nombre determinista viene de la forma en que est definida lafuncin de transicin: si en un instante t la mquina est en elestado q y lee el smbolo a entonces, en el instante siguiente t + 1 lamquina cambia de estado y sabemos con seguridad cual es elestado al que cambia, que es precisamente (q, a).
14Puntos: 1
7/30/2019 AUTOMOTAS
32/33
El nombre "finito" en un Autmata, se justifica por una de lassiguientes afirmaciones. Seleccione una.Seleccione una respuesta.
a. Que el Autmata contiene un
alfabeto smbolos (letras delabecedario) y estas son finitas.
b. Del hecho que el Autmataalmacena informacin en un soloestado (el final), que es dondetermina su recorrido
Incorrecto. Los autmataspueden almacenarinformacin en cualquierestado dependiendo de ladescricpcin de su funcinde transicin.
c. Del hecho que el autmata solo
tiene un conjunto finito de estadosdistintos para recordar lo procesado(no tiene ningn sistema dealmacenamiento de informacinadicional)
d. Que el Autmata tiene un soloestado Inicial que se puederepresentar por un * o por un crculodoble.
IncorrectoPuntos para este envo: 0/1.
Al describir una mquina de estados finitos en particular, debemosincluir las informaciones que varan de un autmata a otro; es decir,no tiene sentido incluir descripciones generales aplicables a todoautmata. Estas informaciones son exactamente las que aparecenen un diagrama de estados y transiciones.
15Puntos: 1Con referencia a los AFD, identifique cual caracterstica no aplica asu descripcin o funcionamiento.Seleccione una respuesta.
a. Para un automata finito no determinista siempre podran
7/30/2019 AUTOMOTAS
33/33
recorrerse una o mas rutas distintas al leer una cadena dada, ypor tanto todas deberan examinarse para verificar si algunatermina en un estado de aceptacion.
b. En un automata finito no determinista puede haber cero, una
o mas transiciones desde un estado leyendo el mismo simbolode entrada que conduzcan a estados diferentes (o posiblementeal mismo).
c. Los automatas finitos tienen un numero finito de estados.
d. En un automata finito determinista para cada estado existeexactamente una transicion por cada simbolo del alfabeto de lamaquina.
CorrectoPuntos para este envo: 1/1.
5267 Continuar 5265