Turing Machine Exercise

INTRODUCCIÓN:

• Los lenguajes independientes del contexto que también se conocen con el nombre de gramáticas de contexto libre son un método recursivo sencillo de especificación de reglas gramaticales con las que se pueden generar cadenas de un lenguaje.
• Es factible producir de esta manera todos los lenguajes regulares, además de que existen ejemplos sencillos de gramáticas de contexto libre que generan lenguajes no regulares. Las reglas gramaticales de este tipo permiten que la sintaxis tenga variedad y refinamientos mayores que los realizados con lenguajes regulares, en gran medida sirven para especificar la sintaxis de lenguajes de alto nivel y otros lenguajes formales.

OBJETIVO GENERAL:

• Conocer los modelos de computación que corresponden a los lenguajes estructurados pro frases, Máquinas de Turing y su aplicación.

OBJETIVOS ESPECÍFICOS:

• Generalizar los conceptos de Máquinas de Turing
• Comprender el diseño y funcionalidad de una MT.
• Reconocer el potencial de procesamiento del lenguaje del autómata con las MT.
• Aplicar un ejercicio enfocado a la máquina de estados (Aplicabilidad de las MT y de
• Autómatas).

EJERCICIOS A DESARROLLAR:

EJERCICIO 1: Diseñe una MT que reconozca el lenguaje de cadenas Máquina que acepta el lenguaje de palabras sobre {0,1} que comienzan y acaban con el mismo símbolo

1. Identifique los componentes de la Máquina de Turing (descríbala).

Una máquina de Turing con una sola cinta puede definirse como una 7-tupla

Definimos una máquina de Turing sobre el alfabeto, donde 0 representa el símbolo blanco. La máquina comenzará su proceso situada sobre un símbolo "1" de una serie.

La máquina de Turing copiará el número de símbolos "1" que encuentre hasta el primer blanco detrás

de dicho símbolo blanco. Es decir, posiciona el cabezal sobre el 1 situado en el extremo izquierdo,

doblará el número de símbolos 1, con un 0 en medio. Así, si tenemos la entrada "111" devolverá

"1110111", con "1111" devolverá "111101111", y sucesivamente.

El conjunto de estados es y el estado inicial es. La tabla que describe la función de transición es la

siguiente:

El funcionamiento de una computación de esta máquina puede mostrarse con el siguiente ejemplo

(en negrita se resalta la posición de la cabeza lectora/escritora):

2. Diséñela en un Diagrama de Moore

3. Recorra la máquina con al menos una cadena válida.

La MT para porque quedó en un estado de aceptación y la cadena es reconocida

4. Identifique una cadena que no sea válida y justifíquela porque.

La MT para porque quedó en un estado de no aceptación y la cadena no es reconocida

No se seguiría el recorrido.

5. Ejecute el RunTest a la cadena aceptada (muéstrela en la captura de imagen para el

trabajo)

6. Identifique en qué momento la máquina se detiene

EJERCICIO 2.

Tomando como referencia la aplicabilidad de las máquinas de estados, la Teoría de la

Información trata una de las técnicas de detección y corrección de errores, por los teoremas

de Trellis y Viterbi con códigos convolucionales para canales con ruido.

Dado el siguiente dato de entrada. 10100110

1. Determine los estados presentes: (represente la máquina de estados) del código

convolucional para k=1 , m= 3, n=2 para cada estado

R/

El código queda especificado por tres parámetros (n, k, m):

n es el número de bits de la palabra codificada.

k es el número de bits de la palabra de datos.

m es la memoria del código o longitud restringida

El número de bits por palabra de datos k, cumple: R=k/n.

A este cociente se le denomina ratio del codificador. He definido para esta aplicación un codificador

convolucional (2,1,3), es decir: un bit para representar la palabra de datos, dos bits de palabra de

codificación por cada bit de palabra de datos y tres bits de longitud de registro. En nuestro caso el

ratio es ½.

2. Determine las entradas codificadas:

3. Realice el diagrama de árbol

4. Realice el diagrama general de estados

6. Asuma que hubo error en los bits 4,6 y 8 con distancia de Hamming 1.

CONCLUSIONES

1. Sin lugar a duda los diagramas de Trellis y Viterbi son una herramienta poderosa para eliminar errores de ruido.
2. La herramienta de conversiones presenta excelentes ventajas, lo mismo que la herramienta de minimización que permite ver en modo simulado y secuencial el proceso mismo.

=========================

JAVA

class HelloDavid {

        

  public static void main(String[] args) {

        String C1D = "HEAD";

        String C2D = "HEAD";

        String C3D = "HEAD";

        int C1,C2,C3,I,Toss=0;

        I=55;

        System.out.println("Flip Three coins "); 

    while (I==55) {

         C1= (int) Math.round(Math.random()*10);

         C2= (int) Math.round(Math.random()*10);

         C3= (int) Math.round(Math.random()*10);

         Toss = Toss + 1;

         if (C1<5) { C1D="HEAD"; } else { C1D="SEAL"; }

         if (C2<5) { C2D="HEAD"; } else { C2D="SEAL"; }

         if (C3<5) { C1D="HEAD"; } else { C3D="SEAL"; }

         System.out.println("Toss:"+ Toss +" Coin1:"+ C1D + " Coin2:"+ C2D + " Coin3:"+ C3D ); 

         if ((C1>4)&(C2>4)&(C3>4)) {  I=60; }    

          }

      

    System.out.println("Finish Target!");

    

  }

}

=========================================================

Flip Three coins 

Toss:1 Coin1:HEAD Coin2:SEAL Coin3:HEAD

Toss:2 Coin1:HEAD Coin2:SEAL Coin3:SEAL

Toss:3 Coin1:HEAD Coin2:SEAL Coin3:SEAL

Toss:4 Coin1:HEAD Coin2:HEAD Coin3:SEAL

Toss:5 Coin1:HEAD Coin2:HEAD Coin3:SEAL

Toss:6 Coin1:HEAD Coin2:SEAL Coin3:SEAL

Toss:7 Coin1:HEAD Coin2:SEAL Coin3:SEAL

Toss:8 Coin1:HEAD Coin2:SEAL Coin3:SEAL

Toss:9 Coin1:HEAD Coin2:SEAL Coin3:SEAL

Toss:10 Coin1:HEAD Coin2:SEAL Coin3:SEAL

Toss:11 Coin1:HEAD Coin2:SEAL Coin3:SEAL

Toss:12 Coin1:HEAD Coin2:SEAL Coin3:SEAL

Toss:13 Coin1:HEAD Coin2:HEAD Coin3:SEAL

Toss:14 Coin1:HEAD Coin2:SEAL Coin3:SEAL

Toss:15 Coin1:HEAD Coin2:HEAD Coin3:SEAL

Toss:16 Coin1:SEAL Coin2:SEAL Coin3:SEAL

Finish Target!

==============================================================

===============================================================

CODIGO POSTAL 

import java.io.*;

import java.util.*;

class CanadaPostCode {

public static void main(String[] args)  {

  

  

      Scanner kb = new Scanner(System.in);

        System.out.println("ENTER CANADIAN POSTAL CODE:");

        char CharPostCode[] = kb.nextLine().toCharArray();

        boolean ValidPostCode = false;

        int LenPostalCode = CharPostCode.length;

        

 if (LenPostalCode != 7) {System.out.println("Canadian Postal Code Entered NOT VALID");}

        

 if (LenPostalCode == 7) {

    if (Character.isLetter(CharPostCode[0]) && Character.isDigit(CharPostCode[1]) && 

        Character.isLetter(CharPostCode[2]) && Character.isWhitespace(CharPostCode[3]) &&

        Character.isDigit(CharPostCode[4])  && Character.isLetter(CharPostCode[5]) &&

        Character.isDigit(CharPostCode[6]) )

        {  ValidPostCode = true; System.out.println("Canadian Postal Code is VALID :) ");}

       else {   System.out.println("Canadian Postal Code Entered is NOT valid :(");}  

                       }

  System.out.println( "Length : "+ LenPostalCode );

  System.out.println("Canada Post Code Entered: ");

  System.out.println(CharPostCode );

  System.out.println("Goodbye");

           }

 }

======================================================