Программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке




Скачать 426.05 Kb.
НазваниеПрограмма, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке
страница3/11
Дата публикации27.03.2013
Размер426.05 Kb.
ТипПрограмма
uchebilka.ru > Информатика > Программа
1   2   3   4   5   6   7   8   9   10   11
^

Недетерминированные КА. Преобразование НКА в КА


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

НКА = {K, ∑, δM, SM, F}, где K – состояние, ∑ - вх. алфавит, δМ – ф-ции переключения состояний, SМ – мн-во начальных состояний, F – допускающие состояния.

Входная цепочка длины n допускается НКА, если существует последовательность состояний S0…Sn такая, что S0 – нач. состояние, Sn - допускающее и для всех  состояние Si принадлежит мн-ву новых состояний, приписанных функцией переходов состоянию Si-1 для i-го элемента входной цепочки.

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





0

1




→A

A, B

C

0

→B

B

C

1

C




A,C

1
A,B – нач. состояния. Цепочка 11 (B→C→C и B→C→A) будет допущена автоматом, т.к. достаточно одной последовательности выборов, приводящей к допускающему состоянию. Цепочка 10 отвергается автоматом, т.к. пустая ячейка означает пустое мн-во.

Пример 2: НКА, допускающий цепочки ЛАССО и ЛАНЬ. Вх. алфавит: {Н, С, Л, О, А, Ь}.





Н

С

Л

О

А

Ь







с0







Л1, Л2










0

нач. сост.

Л1













А1




0

Л в ЛАССО

А1




С1













0

А в ЛАССО

С1




С2













0

1 С в ЛАССО

С2










О







0

2 С в ЛАССО

О



















1

О в ЛАССО

Л2













А2




0

Л в ЛАНЬ

А2

Н
















0

А в ЛАНЬ

Н
















Ь

0

Н в ЛАНЬ

Ь



















1

Ь в ЛАНЬ
Перевод НКА в КА: для каждого НКА существует эквивалентный КА. Шаги построения КА из НКА:

Шаг 1. Пометить первую строку таблицы переходов для КА мн-вом нач. сост. НКА. Применить к этому мн-ву шаг 2.

Шаг 2. По данному мн-ву состояний S, помечающему строку таблицы переходов КА, для которой переходы еще не вычислены, вычислить те сост. НКА, которые могут быть достигнуты из S с с помощью каждого вх. симв. X и поместить мн-ва послед. состояний в соотв. ячейки таблицы КА





Н

С

Л

О

А

Ь




{c0}







{Л1,Л2}










0

{Л1,Л2}













{A1,А2}




0

{A1,А2}

{H}

{C1}













0

{C1}




{C2}













0

{C2}










{O,Ь}







0

{H}
















{O,Ь}

0

{O,Ь}



















1

{ }



















0
Шаг 3. Для каждого нового мн-ва, порожд. переходами на шаге 2, проверить, имеется ли уже в КА строка, помеченная этим мн-вом. Если да – создать строку, если нет – действий не требуется.

Шаг 4. Если в КА есть строка, для кот. не вычислены переходы – вернуться к шагу 2. Если нет – идем на шаг 5.

Шаг 5. Пометить строку, как допускающее состояние КА, если она содержит допускающее состояние НКА. Иначе пометить как отвергающее состояние.
1   2   3   4   5   6   7   8   9   10   11

Похожие:

Программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке iconМетодические указания к лабораторной работе №1 по курсу Информатика для студентов
Написание программы на языке программирования. Программы, написанные на языке C++, имеют расширение. Срр

Программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке iconКурс «Компонентные программные технологии» 1 Лабораторная работа...
Однако для реализации этой системы необходимо разработать исходный текст программы на некотором языке программирования (C++, Pascal,...

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

Программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке iconПрограммирование
Введение в программирование на языке Pascal. Программа. Структура программы. Идентификатор. Правила записи идентификатора. Блок описаний....

Программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке iconПрограмма написана на языке программирования Delphi под ос windows Vista
Не забудьте указать номер версии в любом докладе о проблеме. Кроме того, необходимо постоянно обновлять программу и использовать...

Программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке iconПрограмма аппроксимации на языке бэйсик см-1
Для подготовки исходных данных, необходимых при построении датчиков с заданным распределением в gpss-моделях, описанный алгоритм...

Программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке iconПрограммирование на языке С++ Лабораторный практикум
Цель: Изучение символьных и строковых переменных и способов их обработки в языке Си

Программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке iconНеотъемлемое право личности?
«образование должно быть направлено на полное развитие человеческой личности», а такое развитие возможно только в том случае, если...

Программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке iconРазработка программы на ассемблере. Создание исходного текста программы,...
Целью работы является изучение технологии написания и отладки программ на языке ассемблера

Программа, обеспечивающая преобразование входной программы на некотором языке в выходную программу на другом языке iconО том, как создавать программы на встроенном в Microsoft Office языке...
Но теория будет еще полезнее, если подкрепить ее практикой примерами реально работающих программ, написанных на этом языке. А таких...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
uchebilka.ru
Главная страница


<