Loading...

​​Revisión #3 : Batería de ejercicios

​​Sección 1: MT para MTs

​​Pregunta 1

​​Diseñe una máquina de Turing que cuente el número de veces que una transición sale de un estado en una codificación de máquina de Turing (la cuenta puede ser con marcas del tipo |, |=1, ||=2, |||=3, etc)

1. ​​Identifique el lenguaje aceptado por la máquina de Turing

2. ​​Identifique una cadena aceptada por la máquina de Turing

3. ​​Identifique una cadena rechazada por la máquina de Turing

4. ​​Diseñe la Máquina de Turing

​​Pregunta 2

​​Diseñe una máquina de Turing que cuente el número de veces que una transición llega a un estado en una codificación de máquina de Turing (la cuenta puede ser con marcas del tipo |, |=1, ||=2, |||=3, etc)

1. ​​Identifique el lenguaje aceptado por la máquina de Turing

2. ​​Identifique una cadena aceptada por la máquina de Turing

3. ​​Identifique una cadena rechazada por la máquina de Turing

4. ​​Diseñe la Máquina de Turing

​​Pregunta 3

​​Diseñe una máquina de Turing que cuente el número de loops de tamaño de un símbolo básico en una codificación de máquina de Turing (la cuenta puede ser con marcas del tipo |, |=1, ||=2, |||=3, etc)

1. ​​Identifique el lenguaje aceptado por la máquina de Turing

2. ​​Identifique una cadena aceptada por la máquina de Turing

3. ​​Identifique una cadena rechazada por la máquina de Turing

4. ​​Diseñe la Máquina de Turing

​​Pregunta 4

​​Diseñe una máquina de Turing que cuente el número de veces que un símbolo  sustituyen a otro en en una codificación de máquina de Turing (la cuenta puede ser con marcas del tipo |, |=1, ||=2, |||=3, etc)

1. ​​Identifique el lenguaje aceptado por la máquina de Turing

2. ​​Identifique una cadena aceptada por la máquina de Turing

3. ​​Identifique una cadena rechazada por la máquina de Turing

4. ​​Diseñe la Máquina de Turing

​​Sección 2: Jerarquía de Chomsky extendida

​​Pregunta 5

​​

​​Con libertad artística dibuje la jerarquía de Chomsky extendida. Para inspiración revise los siguientes links:

​​Jerarquía de Chomsky extendidas hechas por el curso 2020-I

​​Jerarquía de Chomsky extendidas hechas por el curso 2019-II

​​Jerarquía de Chomsky extendidas hechas por el curso 2019-I

​​Jerarquía de Chomsky extendidas hechas por el curso 2018-II

​​Jerarquía de Chomsky extendidas hechas por el curso 2018-I

​​Jerarquía de Chomsky extendidas hechas por el curso 2017-II

​​Jerarquía de Chomsky extendidas hechas por el curso 2016-II

​​Jerarquía de Chomsky extendidas hechas por el curso 2016-I

​​