Цель работы. Основные сведения из теории. Реализация алгоритма в табличной форме. Листингпрограммы

ГУАП

КАФЕДРА № 43

ОТЧЕТ
ЗАЩИЩЕН С ОЦЕНКОЙ

ПРЕПОДАВАТЕЛЬ


должность, уч. степень, звание		подпись, дата		инициалы, фамилия

ОТЧЕТ О ЛАБОРАТОРНОЙ РАБОТЕ №2

Изучение принципов функционирования машины Тьюринга

по дисциплине: ТЕОРИЯ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ

РАБОТУ ВЫПОЛНИЛ

СТУДЕНТ ГР.					Р. В. Яровой
			подпись, дата		инициалы, фамилия

Санкт-Петербург2017

Цель работы

Необходимо составить алгоритмвычисления 3х-у для машины Тьюринга в табличном виде. Написать реализацию МТ на любом высокоуровневом языке.

Основные сведения из теории

Основные понятия МТ:

1) Устройство управления УУ-> Ø ={q0, q1,..., qn}

2) Бесконечная лента, разбитая на ячейки в которых может быть забиты символы из

A = {a1, a2, …, an}

3) Списывание и записывание головки, в каждый момент времени обозревающей одну ячейку.

Принцип функционирования МТ:

В такт работы МТ находится в одном из своих дискретных состояний. Головка обозревает одну ячейку. Через такт времени машина переходит в новое состояние или остается в старом. В обозреваемую ячейку заносится новый символ. Головка переходит в лево или право на одну ячейку или остается на месте.

Реализация алгоритма в табличной форме

Листингпрограммы

КлассTable

package src. main. java;

import java. util. HashMap;
import java. util. List;
import java. util. Map;

public class Table {
private Map< String, Integer> rows;
private Map< String, Integer> columns;
private String[][][] table;

public Table(List< String> rules) {
this. rows = new HashMap< > ();
   this. columns = new HashMap< > ();
String[] alphabet = rules. remove(0). split(" " );
String[] states = rules. remove(0). split(" " );
table = new String[alphabet. length][states. length][3];
   for (int j = 0; j < alphabet. length; j++)
rows. put(alphabet[j], j);
   for (int j = 0; j < states. length; j++)
columns. put(states[j], j);
String[] s;
   for (String rule: rules) {
       s = rule. split(" " );
table[rows. get(s[0])][columns. get(s[1])][0] = s[2];
table[rows. get(s[0])][columns. get(s[1])][1] = s[3];
table[rows. get(s[0])][columns. get(s[1])][2] = s[4];
}
}

public String[] getCeil(String row, String column){
return table[rows. get(row)][columns. get(column)];
}
}

КлассTrace

package src. main. java;

import java. io. FileWriter;
import java. io. IOException;

/**
* Created by slava on 15. 10. 2017.
*/
public class Trace {
private FileWriter fw;
private int countWhiteSpaces;

public Trace(String outputFile) {
try {
fw = new FileWriter(outputFile, false);
} catch (IOException e) {
e. printStackTrace();
}
}

public void run(Table table, String str) throws IOException {
char[] example = str. toCharArray();
String state = " q1";
String[] ceil;
do {
fw. write(example);
ceil = table. getCeil(String. valueOf(example[countWhiteSpaces]), state);
example[countWhiteSpaces] = ceil[0]. charAt(0);
printWhiteSpaces(ceil[1]);
state = ceil[2];
} while (! state. equals(" stop" ));

}

private void printWhiteSpaces(String pattern) throws IOException {
if (pattern. equals(" > " )) {
fw. write(" \n" );
for (int i = 0; i < countWhiteSpaces; i++) {
fw. write(" " );
}
fw. write(" ^\n" );
countWhiteSpaces++;
} else if (pattern. equals(" < " )) {
fw. write(" \n" );
for (int i = 0; i < countWhiteSpaces; i++) {
fw. write(" " );
}
fw. write(" ^\n" );
countWhiteSpaces--;
}
fw. flush();
}
}

КлассMain

package src. main. java;

import java. io. IOException;
import java. nio. charset. StandardCharsets;
import java. nio. file. Files;
import java. nio. file. Paths;
import java. util. Arrays;
import java. util. HashSet;
import java. util. List;
import java. util. Set;
import java. util. stream. Collectors;

public class Main {
public static void main(String[] args) throws IOException {
   List< String> lines = Files. readAllLines(Paths. get(" rules. txt" ), StandardCharsets. UTF_8);
String example = lines. remove(0);
//----------------------
char[] chars = example. toCharArray();
Set< String> set = new HashSet< > ();
   for (int i = 0; i < chars. length; i++) {
       set. add(String. valueOf(chars[i]));
}
   String[] split = lines. get(0). split(" " );
HashSet< String> collect = Arrays. stream(split). collect(Collectors. toCollection(HashSet:: new));
set. removeAll(collect);
   if(set. size()! = 0){
       System. err. println(" Ошибка. Влентеприсутствсимволывнеалфавита! " );
}

//----------------------
Table table = new Table(lines);
Trace trace = new Trace(" trace. txt" );
trace. run(table, example);
}
}

12 Следующая ⇒