Построить конечный автомат для распознания регулярного множества цепочек трехсимвольного алфавита

Построить конечный автомат (КА–распознаватель) для распознания регулярного множества цепочек трехсимвольного алфавита в соответствии с описанием:

Содержит два символов “а”, заканчивается на “ b ”, а символы “а” и "с " не стоят рядом.

0

В чём проблема?

1

AdmiralHood, Я сам заочник, ни капли не знаю о чем идёт речь. Скоро экзамен, нужна срочная помощь.

0

А здесь ничего не надо знать. Здесь чистая незамутнённая логика. Формулируете, что вам нужно. А нужно, чтобы в строчке два раза встретились буквы a, причём ни перед, ни после них не стояла буква c, и строчка кончалась на b.

Автомат можно задавать разными способами. Один из них — задание в виде графа. Граф — это куча состояний, которые обозначают кружочками. Состояния связаны между собой стрелочками. По стрелочкам автомат переходит от одного состояния к другому. Причём переход возможен только по очередной букве. Каждая буква — это инструкция, которая говорит автомату, в какое состояние ему надо переходить.

Здесь самое главное понять, как автомат запоминает информацию о предыдущих событиях. Вот представьте себе, что у человека специфическое расстройство памяти. Он не помнит, что было вчера. У него есть дом, в доме 100 комнат, и каждая комната что-то означает. Если, например, он утром проснулся в комнате № 23, это значит, что надо позвонить родителям. Если в комнате 56, значит сегодня будет корпоратив. А если в комнате 82, значит и то, и другое. Точно так же автомат. Комната – это состояние. Автомат не помнит, что было раньше. Вся его память заключается в том, в каком состоянии он в данный момент находится. Ваша задача придумать минимальный набор состояний, которые покрывают все существенные для решения вашей задачи ситуации.

Начинаете строить автомат с исходного состояния, которое я обозначу 0. Это состояние означает «не пришло ещё ни одной буквы а, и предыдущая буква была не с». Почему нас волнуют именно буквы а и с? Буква а вообще имеет глобальное значение. Нам нужно их пересчитать и убедиться, что их ровно две. Если больше или меньше, значит строка неправильная. Буква с нас интересует постольку-поскольку за ней не должна следовать буква а, иначе строка тоже будет неправильной.

Если автомат в состоянии 0 получает букву а, он переходит в состояние 1. Оно означает «пришла первая буква а, и перед ней не было буквы с». По букве с автомат переходит из состояния 0 в состояние 2. Оно означает «не было ещё ни одной буквы а, а предыдущая буква была с».

Далее, если в состоянии 1 пришла буква c, то это ошибка, автомат должен перейти в какое-то состояние, которое будет означать ошибку. Из этого состояния автомат не должен выходить и по любой букве должен возвращаться в него. Это состояние я условно обозначу 99. В состояние 99 автомат также должен перейти из состояния 2 по букве а.



Желательно, чтобы из каждого состояния по любой букве можно было бы куда-то перейти. Поэтому в каждом состоянии должен быть определён переход по любой букве. Что будет, если в состоянии 1 придёт буква b? Автомат должен перейти в состояние 3, которое означает «была уже одна буква а, и предыдущая буква была не с».

Что будет, если в состоянии 1 придёт буква a? Автомат должен перейти в состояние 4, которое означает «было уже две буквы а, и предыдущая буква была не с».

Что будет, если в состоянии 2 придёт буква b? Нужно вернуться в состояние 0. Что будет, если в состоянии 2 придёт буква с? Нужно остаться в состоянии 2.



И так перебираете каждое состояние по каждой букве. Должно получиться что-то типа

1

AdmiralHood, Огромное тебе спасибо! ты столько сделал! можно с тобой связаться лично в Вк или по почте? Есть ещё один вопрос. Напиши мне сюда:del

	Комментарий модератора
	Правила форума 4.6. Обсуждение вопросов - только в теме на форуме. Приглашения к обсуждению еще где-либо (в том числе и с помощью системы личных сообщений) запрещены, за исключением коммерческих разделов. 4.12. Не стоит просить или предлагать выслать ответ в icq, e-mail и другие средства общения. Эта просьба все равно не будет выполнена, а сообщение будет отредактировано модератором.

0