Понятие машины тьюринга. формальные грамматики.

      Комментарии к записи Понятие машины тьюринга. формальные грамматики. отключены

Машина Тьюринга – математическая, воображаемая машина, а не машина физическая. Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

Устройство машины Тьюринга

В состав машины Тьюринга входит бесконечная в обе стороны лента, разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.

Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.

Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма.

Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара «ленточный символ — состояние», для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной.

Пример.

Дана МТ с внешним алфавитом А= {0,1} Q={q0,q1,q2}.

q11 — q11
q10 — q20 П
q21 — q21 П
q21 — q21 П
q20 — q01

q111011

Выполняем предписания алгоритма:

q111011

1 q11011

11 q1011

110 q211

1101 q21

11011 q20

11011 q01

q111011 = 11011 q01

Формальная грамматика или просто грамматика в теории формальных языков — способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавита.

Формальные грамматики имеют обозначение: G.

L(G) – формальный язык, заданный формальной грамматикой G.

Формальная грамматика — это математическая структура вида:

G ={V, W, I, P}, где

V – словарь терминальных символов: a, b, c;

W – словарь нетерминальных символов: A, B, C;

I — аксиома грамматики ;

P — совокупность правил вывода или продукций.

Различают порождающие и распознающие (или аналитические) грамматики — первые задают правила, с помощью которых можно построить любое слово языка, а вторые позволяют по данному слову определить, входит оно в язык или нет.

  • Терминал (терминальныйсимвол) — объект, непосредственно присутствующий в словах языка,соответствующего грамматике, и имеющий конкретное, неизменяемое значение(обобщение понятия «буквы»). В формальных языках, используемых накомпьютере, в качестве терминалов обычно берут все или часть стандартныхсимволов ASCII —латинские буквы, цифры и спец. символы.
  • Нетерминал(нетерминальный символ) — объект, обозначающий какую-либо сущностьязыка (например: формула, арифметическое выражение, команда) и не имеющийконкретного символьного значения.

Типы грамматик — ?

По иерархии Хомского, грамматики делятся на 4 типа, каждый последующий является более ограниченным подмножеством предыдущего (но и легче поддающимся анализу):

  • тип 0. неограниченные грамматики —возможны любые правила
  • тип 1. контекстно-зависимые грамматики —левая часть может содержать один нетерминал,окруженный «контекстом» (последовательности символов, в том же виде присутствующиев правой части); сам нетерминал заменяетсянепустой последовательностью символов в правой части.
  • тип 2. контекстно-свободные грамматики —левая часть состоит из одного нетерминала.
  • тип 3. регулярные грамматики — болеепростые, эквивалентны конечным автоматам.

Статьи к прочтению:

Лекция 8: Формальные грамматики


Похожие статьи: