27275477
Description
Mind Map by Valeria González, updated more than 1 year ago
|
Created by Valeria González
about 4 years ago
|
|
Autómatas y lenguajes formales.
- Autómata
- Modelo computacional
consiste en un conjunto de
estados bien definidos,un
estado inicial,un alfabeto de
entrad y una función de
transición.
- El autómata mas conocido en el
mundo es el denominado "MAQUINA
DE TURING"
- Modelo computacional
consiste en un conjunto de
estados bien definidos,un
estado inicial,un alfabeto de
entrad y una función de
transición.
- Historia.
- Los autómatas existen desde la
antiguedad, pero en el siglo XVII
cuando en Europa habia pasion por la
tecnica. se perfeccionaron cajas de
musica con cilindro de puas.
- Fueron inspirados por los pajaros autómatas que habia en
Bizancio , los cuales podian cantar y silbar.
- Fueron inspirados por los pajaros autómatas que habia en
Bizancio , los cuales podian cantar y silbar.
- En el siglo XVIII ROENTGEN Y
KINTZLING mostrarn con LUIS
XVI la autómata figura humana
llamada "la tañedora de salterio"
- Otros inventores son PIERRE JACQUET DROZ autor de
"el dibujante" y "los musicos" M.VAUCANSON autor del
"pato digeridor"
- Los autómatas existen desde la
antiguedad, pero en el siglo XVII
cuando en Europa habia pasion por la
tecnica. se perfeccionaron cajas de
musica con cilindro de puas.
- DIAGRAMA DE ESTADO
- permite visualizar los estados como circulos que en
su interior registran su significado.
- Existen flechas que
representan la transicion
entre estados y la notacion
de ENTREDA/SALIDA que provoca la transicion de estados
- Existen flechas que
representan la transicion
entre estados y la notacion
de ENTREDA/SALIDA que provoca la transicion de estados
- TABLA DE ESTADO
- conformada por descripción de l estado actual,
descripción de la entrada, descripción del estado
siguiente, descripción de las salidas.
- CADENA VACIA.
- Es vacía cuando la longitud de caracteres que utiliza es igual a cero.
- es una cadena que
no tiene caracteres
asociados.
- es una cadena que
no tiene caracteres
asociados.
- Es vacía cuando la longitud de caracteres que utiliza es igual a cero.
- conformada por descripción de l estado actual,
descripción de la entrada, descripción del estado
siguiente, descripción de las salidas.
- permite visualizar los estados como circulos que en
su interior registran su significado.
- ALFABETO.
- conjunto de todos los símbolos validos o posibles para una
aplicación.
- el alfabeto
puede ser
finito o tan
simple
como el
alfabeto
binario para
representar
expresion
de entreda
,salida,estado.
- el alfabeto
puede ser
finito o tan
simple
como el
alfabeto
binario para
representar
expresion
de entreda
,salida,estado.
- GRAMÁTICAS FORMALES.
- Es una coleccion estructurada de palabras y
frases ligadas por reglas que definen el
conjunto de cadenas de caracteres que
representan los comandos completos que
pueden ser reconocidos por un motor de
discurso.
- Es una coleccion estructurada de palabras y
frases ligadas por reglas que definen el
conjunto de cadenas de caracteres que
representan los comandos completos que
pueden ser reconocidos por un motor de
discurso.
- GRAMÁTICA.
- Es definir y enumerar las palabras y frases
validas de un lenguaje.
- La forma general definida por BNF es denominada regla
de producción y se puede representar.
- < regla > = sentencias y frases.
- Las partes de formas general BNF.
- el lado izquierdo o regla es el identificador único de las
reglas definidas para el lenguaje. puede ser cualquier
palabra, con la condición de estar encerrada.
- el operador de asignación
= es un elemento
obligatorio.
- el delimitador de fin de
instrucción es un elemento
obligatorio.
- el delimitador de fin de
instrucción es un elemento
obligatorio.
- el lado
derecho o
sentencias y
frases,
define todas
las
posibilidades
validas
en
la
gramática
definida.
- el lado izquierdo o regla es el identificador único de las
reglas definidas para el lenguaje. puede ser cualquier
palabra, con la condición de estar encerrada.
- < regla > = sentencias y frases.
- La forma general definida por BNF es denominada regla
de producción y se puede representar.
- JERARQUIZACION DE GRAMÁTICAS.
- las gramáticas pueden ser de
distintos tipos, de acuerdo con las
características que rigen la
formulación de reglas de
producción validas.
- Los cuales parten de
las gamáticas
arbitrarias que son
aquellas que
consideran la
existencia infinita
de cadenas
formadas por
simbolos del
lenguaje.
- Los cuales parten de
las gamáticas
arbitrarias que son
aquellas que
consideran la
existencia infinita
de cadenas
formadas por
simbolos del
lenguaje.
- GRAMÁTICAS SENSIBLES AL CONTEXTO
- Tiene la característica de que el lado
derecho de la regla de producción
siempre debe ser igual o mayor que
el lado izquierdo.
- GRAMÁTICAS INDEPENDIENTES DEL CONTEXTO
- Es aquella que cumple con las
propiedades de la gramática sensible al
contexto ,la caracteristica de que el
lado izquierdo de la regla de
produccion solo debe tener un
elemento y este no puede ser un
elemento terminal.
- GRAMÁTICAS REGULARES.
- Es cuando cumple con las caracteristicas de la gramática independiente del
contexto y ademas se restringe atraves de las reglas de produccion para
generar solo reglas de los dos tipos anteriores.
- Es cuando cumple con las caracteristicas de la gramática independiente del
contexto y ademas se restringe atraves de las reglas de produccion para
generar solo reglas de los dos tipos anteriores.
- Es aquella que cumple con las
propiedades de la gramática sensible al
contexto ,la caracteristica de que el
lado izquierdo de la regla de
produccion solo debe tener un
elemento y este no puede ser un
elemento terminal.
- Tiene la característica de que el lado
derecho de la regla de producción
siempre debe ser igual o mayor que
el lado izquierdo.
- las gramáticas pueden ser de
distintos tipos, de acuerdo con las
características que rigen la
formulación de reglas de
producción validas.
- Es definir y enumerar las palabras y frases
validas de un lenguaje.
- conjunto de todos los símbolos validos o posibles para una
aplicación.
- FRASE
- es la asociación de un conjunto de simbolos definidos en
un alfabeto que tiene la propiedad de tener sentido,
significado y lógica.
- Las frases parten del
establecimiento de un
vocabulario que
define las palabras
validas del lenguaje
sobre la base del
alfabeto definido.
- Las frases parten del
establecimiento de un
vocabulario que
define las palabras
validas del lenguaje
sobre la base del
alfabeto definido.
- es la asociación de un conjunto de simbolos definidos en
un alfabeto que tiene la propiedad de tener sentido,
significado y lógica.
- LENGUAJE.
- Conjunto de cadenas que
obedecen a un alfabeto fijado.
- Conjunto de cadenas que
obedecen a un alfabeto fijado.
- LENGUAJE FORMAL.
- Esta constituido por un
alfabeto,un vocabulario y
un conjunto de reglas de
producción definidas por
gramáticas.
- Frases validas en lenguaje
formal son aquellas que se
crean con los símbolos y
palabras definidas tanto en el
alfabeto como en el
vocabulario del lenguaje.
- Frases validas en lenguaje
formal son aquellas que se
crean con los símbolos y
palabras definidas tanto en el
alfabeto como en el
vocabulario del lenguaje.
- LENGUAJE INDECIDIBILIDAD.
- Es si los miembros no pueden ser identificados por un algoritmo que restrinja todas las
entradas en un numero de pasos finito.
- Sus propiedades es que no debe ser reconocidos en una entrada valida
en maquina de turing.
- En contraposicion con el lenguaje indecidible y los
problemas asociados a este tipo de lenguajes existen los
problemas decidibles, que esten relacionados con
lenguajes del mismo tipo y que tiene las caracteristicas
opuestas.
- En contraposicion con el lenguaje indecidible y los
problemas asociados a este tipo de lenguajes existen los
problemas decidibles, que esten relacionados con
lenguajes del mismo tipo y que tiene las caracteristicas
opuestas.
- Sus propiedades es que no debe ser reconocidos en una entrada valida
en maquina de turing.
- Es si los miembros no pueden ser identificados por un algoritmo que restrinja todas las
entradas en un numero de pasos finito.
- Esta constituido por un
alfabeto,un vocabulario y
un conjunto de reglas de
producción definidas por
gramáticas.
Want to create your own Mind Maps for free with GoConqr? Learn more.