Некоторые обычные языки конечны - они содержат конечное число строк. Когда у вас есть конечное количество вещей, это означает, что вы можете сосчитать их все и в конце концов дойти до конца; Вы можете записать их все, если они являются словами на языке. Записать все слова на языке - это способ дать исчерпывающее определение языка.
Однако - есть языки, которые не являются конечными. Они не содержат никакого количества слов, которые вы можете считать от начала до конца или когда-либо полностью записывать. Если вы думаете о всех натуральных числах (1, 2,…, 100,…) как о строках на языке десятичных представлений, ясно, что их не конечное число. Их бесконечно много. Вы не можете дать исчерпывающие определения бесконечных языков (за исключением, возможно, многопланового использования многоточия, как я сделал в моем примере). В этих случаях вы должны описать строки, которые включены и / или исключены, и полагаться на читателя, чтобы определить членство в каждом конкретном случае.
Предоставление конечного автомата является одним из совершенно разумных способов дать критерий в соответствии с какое членство в языке может быть определено: пропустите строку через автомат и посмотрите, будет ли она принята. В этом смысле вопрос о том, что такое язык конечного автомата, можно рассматривать как тривиальный: он принимает язык строк, которые оставляют конечный автомат в принимающем состоянии.
Другой способ описания языка - дать грамматика или, для регулярных языков, регулярное выражение. Это не обязательно более или менее полезные способы описания языка, чем тот конечный автомат, который у вас уже есть.
Обычно в курсовой работе, когда вас просят описать язык конечного автомата, вы, вероятно, попросили дать простое определение языка Engli * - простой - из строк, и, возможно, предоставить некоторую запись конструктора множеств. Вот что мы попытаемся сделать здесь.
Ваш NFA зацикливается на q0, принимая любое число a, пока не увидит хотя бы один a. Если он видит b перед a, он падает. После этого, если он видит хотя бы один b, он может принять; он может видеть любое число b, но после начального запуска a он больше никогда не увидит два a подряд. Машина принимает, только если она заканчивается на b.
. Взятые вместе, это может быть описание на простом английском языке sh, которое подходит для этого языка:
Все строки, начинающиеся хотя бы с одного a, заканчивающиеся b и не содержащие подстроку aa после первого экземпляра b.
Регулярное выражение для этого язык aa*(bb*a)*.