​​Serie #3 LFYA 2022-I:Batería de preguntas

​​Sección 1: MT para MTs

​​Pregunta 1

​​Diseñe una máquina de Turing que cuente el número de estados únicos de los que sale una transición en una codificación de máquina de Turing (incluya un pseudocódigo, la cuenta puede ser con marcas del tipo |, |=1, ||=2, |||=3, etc)
  1. ​​Identifique el lenguaje aceptado por la máquina de Turing
  1. ​​Identifique cinco cadenas aceptadas por la máquina de Turing
  1. ​​Identifique cinco cadenas rechazadas por la máquina de Turing
  1. ​​Escriba un pseudocódigo para el problema que funcione en una máquina de Turing
  1. ​​Diseñe una Máquina de Turing

​​Pregunta 2

​​Diseñe una máquina de Turing que cuente el número de estados únicos a los que llega una transición en una codificación de máquina de Turing (incluya  pseudocódigo, la cuenta puede ser con marcas del tipo |, |=1, ||=2, |||=3, etc)
  1. ​​Identifique el lenguaje aceptado por la máquina de Turing
  1. ​​Identifique cinco cadenas aceptadas por la máquina de Turing
  1. ​​Identifique cinco cadenas rechazadas por la máquina de Turing
  1. ​​Escriba un pseudocódigo para el problema que funcione en una máquina de Turing
  1. ​​Diseñe una 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 (incluya  pseudocódigo, , la cuenta puede ser con marcas del tipo |, |=1, ||=2, |||=3, etc)
  1. ​​Identifique el lenguaje aceptado por la máquina de Turing
  1. ​​Identifique cinco cadenas aceptadas por la máquina de Turing
  1. ​​Identifique cinco cadenas rechazadas por la máquina de Turing
  1. ​​Escriba un pseudocódigo para el problema que funcione en una máquina de Turing
  1. ​​Diseñe una Máquina de Turing

​​Pregunta 4

​​Diseñe una máquina de Turing que cuente el número de símbolos únicos que sustituyen a otro en en una codificación de máquina de Turing (Incluya pseudocódigo, , la cuenta puede ser con marcas del tipo |, |=1, ||=2, |||=3, etc)
  1. ​​Identifique el lenguaje aceptado por la máquina de Turing
  1. ​​Identifique cinco cadenas aceptadas por la máquina de Turing
  1. ​​Identifique cinco cadenas rechazadas por la máquina de Turing
  1. ​​Escriba un pseudocódigo para el problema que funcione en una máquina de Turing
  1. ​​Diseñe una 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
​​