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




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

Приведение конечных автоматов


Автомат называется приведенным или минимальным, ели он не содержит недостижимых состояний и никакие два его состояния не эквивалентны друг другу.

Состояние S1 автомата A1 эквивалентно состоянию S2 автомата A2, если автомат A1 находясь в сост. S1 допускает те же цепочки, что и автомат A2 в сост. S2. Если два состояния S1 и S2 одного автомата эквивалентны, то автомат можно упростить, заменив в таблице переходов все вхождения имен этих состояний новым именем, а затем удалив повторяющуюся строку.

Если два состояния не эквивалентны, то любая цепочка, под действием которой одно из них переходит в допускающее состояние, а другое – в отвергающее, называется различающей цепочкой этих двух состояний. Два состояния эквивалентны тогда и только тогда, когда не существует различающей их цепочки.

Два автомата эквивалентны, если их начальные состояния эквивалентны.

Состояние называется недостижимым, если в него нет переходов ни для какой входной цепочки.

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

Пример проверки эквивалентности состояний:

Состояния подобны, если выполняются условия подобия (оба состояния либо допускающие, либо отвергающие) и преемственности (для всех вх. символов сост. S1 и S2 переходят в эквивалентные сост.).





x

y




0

0

3

0

1

2

5

0

2

2

7

0

3

6

7

0

4

1

6

1

5

6

5

0

6

6

3

1

7

6

3

0




x

y

{0,1}

{0,2}

{3,5}

{0,2}

{0,2}

{3,7}

{3,5}

6

{5,7}

{3,7}

6

{3,7}

{5,7}

6

{3,5}




x

y




{0,1,2}

{0,1,2}

{3,5,7}

0

{3,5,7}

6

{3,5,7}

0

4

{0,1,2}

6

1

6

6

{3,5,7}

1





x

y




A

A

B

0

B

6

B

0

4

A

6

1

6

6

B

1



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
Главная страница


<