пользователей: 21251
предметов: 10459
вопросов: 177801
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ


28. Автоматные языки и грамматики. Язык, принимаемый КА. Дерево разбора для автоматных грамматик.

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

Конечным автоматом (КА, конечным недетерминированным автоматом –КНА, конечным распознавателем) называют пятерку

A=(N, T, , S, F),

где

N–конечное множество состояний;

T– конечного множество входных символов (или множество терминальных символов грамматики, алфавит языка;

– функция переходов состояний (в общем случае неоднозначная);

SÎN– начальное состояние;

FÍN– множество заключительных состояний.

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

Говорят, что автомат A принимает (допускает) цепочку, если после подачи на вход этой цепочки автомат переходит в одно из конечных состояний. Множество всех цепочек, переводящих автомат из начального состояния в одно из конечных состояний образует язык, принимаемый (допускаемый) этим автоматом. Если автомат А принимает язык, порождаемый  грамматикой G, то

  • множество состояний автомата А это множество нетерминальных символов  грамматики G;
  • множество входных символов автомата – это множество терминальных символов грамматики G, т.е алфавит языка;
  • функция переходов автомата A задается правилами грамматики G;
  • конечные состояния автомата A это такие нетерминальные символы K грамматик G, для которых существует правило вида K ®e;
  • начальное состояние автомата A, это нецелевой символ грамматики G.

 

Дерево разбора в автоматной грамматике может быть однозначно построено, если задан КА.  КА не только дает ответ на вопрос о принадлежности цепочки языку, но и позволяет выявить структуру цепочки. Правила вида A→a и A→e могут быть использованы в процессе порождения цепочки только один раз. Каждая подстановка вида A→aB приводит к появлению в дереве новой внутренней вершины, помеченной нетерминалом. Ее левая дочерняя вершина помечается терминалом.

 


19.01.2016; 06:42
хиты: 22
рейтинг:0
Точные науки
информатика
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь