Конечные автоматы и формальные языки

Определение детерминированного конечного автомата, способы его задания. Расширенные функции переходов на цепочки. Язык ДКА.

Алфавитом называется конечное непустое множество символов. Пример: бинарный алфавит = {0, 1}. Цепочкой или словом называется любая последовательность символов из некоторого алфавита. - пустая цепочка (пустое слово) не содержит ни одного символа.

Длина слова – число позиций для символов в цепочке. Пример: 01100. Символов – 2 длина – 5. - все слова в алфавите

Множество слов каждое из которых принадлежит называется языком L.

Детерминированным конечным автоматом (ДКА) называется пятерка A = (Q, , , , F)

Q – непустое конечное множество (множество состояний). - алфавит, множество входных символов. - начальное состояние.

F – множество допустимых (заключительных) состояний

,

Язык ДКА – множество всех его допустимых цепочек. Любой ДКА определяет язык, а именно множество всех цепочек приводящих автомат из начального состояния в одно из допускающих. Язык ДКА – множество всех меток вдоль всех маршрутов, ведущих из начального состояния в любое допускающее.

,

- расширенная функция переходов,

Индукция по длине слова

| w | - количество позиций в слове

| w | = 0 , , ,

x – начальное слово, a – алфавитный символ, Язык ДКА A = (Q, , , , F), такие слова, которые приводят начальное состояние в конечное. Язык L называется регулярным, если L = L(A) (если совпадает с языком некоторого автомата).

Определение недетерминированного конечного автомата, способы его задания. Расширенные функции переходов на цепочки. Язык НКА.

НКА обладает свойством находиться в нескольких состояниях одновременно. Эту особенность часто представляют как свойство автомата “делать догадки” относительно его входных данных. Нужно: 1. определить НКА 2. показать, что всякий такой автомат допускает язык допустимый ДКА.

НКА допускает регулярные языки точно так же как и ДКА.

НКА автоматы строить легче, можно преобразовать в ДКА.

A = (Q, , , , F), - функция перехода

Различие ДКА и НКА состоит в типе функции .

НКА функция, аргументами которой являются состояния и элемент входного алфавита, а значениями - множество состоящее из 0,1 или нескольких состояний.

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

Для данного НКА A = (Q, , , , F) язык L(A) есть множество цепочек