Prerrequisito – Máquina de Turing
El lenguaje L = {0 n 1 n 2 n | n≥1} representa un tipo de lenguaje en el que usamos solo 3 caracteres, es decir, 0, 1 y 2. Al principio, el lenguaje tiene un número de 0 seguido de igual número de 1 y luego seguido de igual número de 2. Cualquier string que caiga en esta categoría será aceptada por este idioma. El principio y el final de la string están marcados con el signo $.
Ejemplos –
Input : 0 0 1 1 2 2 Output : Accepted Input : 0 0 0 1 1 1 2 2 2 2 Output : Not accepted
Suposición: Reemplazaremos 0 por X, 1 por Y y 2 por Z
Enfoque utilizado:
primero reemplace un 0 desde el frente por X, luego siga moviéndose a la derecha hasta que encuentre un 1 y reemplace este 1 por Y. Nuevamente, siga moviéndose a la derecha hasta que encuentre un 2, reemplácelo por Z y muévase a la izquierda. Ahora sigue moviéndote hacia la izquierda hasta que encuentres una X. Cuando la encuentres, muévete hacia la derecha, luego sigue el mismo procedimiento que el anterior.
Se produce una condición cuando encuentra una X seguida inmediatamente de una Y. En este punto, nos movemos hacia la derecha y seguimos comprobando que todos los 1 y 2 se han convertido en Y y Z. De lo contrario, no se acepta la string. Si llegamos a $entonces se acepta la string.
- Paso 1:
Reemplace 0 por X y muévase a la derecha, vaya al estado Q1. - Paso 2:
Reemplace 0 por 0 y muévase a la derecha, Permanezca en el mismo estado
Reemplace Y por Y y muévase a la derecha, Permanezca en el mismo estado
Reemplace 1 por Y y muévase a la derecha, vaya al estado Q2. - Paso 3:
Reemplace 1 por 1 y muévase a la derecha, Permanezca en el mismo estado
Reemplace Z por Z y muévase a la derecha, Permanezca en el mismo estado
Reemplace 2 por Z y muévase a la derecha, vaya al estado Q3. - Paso 4:
Reemplace 1 por 1 y muévase a la izquierda, permanezca en el mismo estado
Reemplace 0 por 0 y muévase a la izquierda, permanezca en el mismo estado
Reemplace Z por Z y muévase a la izquierda, permanezca en el mismo estado
Reemplace Y por Y y muévase a la izquierda, permanezca encendido mismo estado
Reemplace X por X y muévase a la derecha, vaya al estado Q0. - Paso 5:
Si el símbolo es Y, reemplácelo por Y y muévase a la derecha y vaya al estado Q4 De lo
contrario, vaya al paso 1 - Paso 6:
Reemplace Z por Z y muévase a la derecha, permanezca en el mismo estado
Reemplace Y por Y y muévase a la derecha, permanezca en el mismo estado
Si el símbolo es $, reemplácelo por $y muévase a la izquierda, SE ACEPTA LA CADENA, VAYA AL ESTADO FINAL P5
Publicación traducida automáticamente
Artículo escrito por RishabhMalik y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA