Как найти язык NFA

Question

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

Answer 1

Некоторые регулярные языки конечны - они содержат конечное число строк. Когда у вас есть конечное количество вещей, это означает, что вы можете пересчитать их все и в конце концов дойти до конца; вы можете записать их все, если это слова на языке. Записывание всех слов на языке - это способ дать развернутое определение языка.

Однако - есть языки, которые не конечны. Они не содержат такого количества слов, которое вы можете сосчитать от начала до конца или когда-либо полностью записать. Если вы думаете обо всех натуральных числах (1, 2, …, 100, …) как о строках на языке десятичных представлений, очевидно, что их не конечное количество. Их бесконечно много. Вы не можете дать развернутых определений бесконечных языков (кроме, возможно, намекного использования многоточия, как я сделал в своем примере). В этих случаях вы должны описать строки, которые включены и / или исключены, и полагаться на читателя, чтобы сделать вывод о членстве в каждом конкретном случае.

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

Другой способ описания языка - дать грамматику или, для обычных языков, регулярное выражение. Это не обязательно более или менее полезные способы описания языка, чем конечный автомат, который у вас уже есть.

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

Ваша NFA зацикливается на q0, принимая любое количество a, пока не увидит хотя бы один a. Если он видитb перед a, происходит сбой. После этого, если увидит хоть одинb, он может принять; он может видеть любое количествоb, но после первого запуска a, он никогда больше не увидит двух aв ряд. Машина принимает, только если заканчиваетсяb.

Взятые вместе, это может быть описание на простом английском языке, подходящее для этого языка:

Все строки, которые начинаются хотя бы с одной a, которые заканчиваются на b и которые не содержат подстроки aa после первого случая b.

Регулярное выражение для этого языка - aa*(bb*a)*.