Предположим, что должен быть спроектирован DFA, который принимает всю строку над Σ = {0,1} *, которая начинается и заканчивается одним и тем же символом (например, 0110, 10101 и т. Д.). приемлемая строка? Это означает, что начало состояния конечное состояние?Начальное состояние для DFA в автоматах
ДА.
Строка ε принадлежит {0,1} * и его начальные и конечные символы не different.so она должна быть принята DFA
Это полностью зависит от того, что имеется в виду. Человеческие языки расплывчаты и неточны; поэтому мы придумываем формализмы, такие как регулярные выражения.
Если это упражнение, я бы спросил, кто дает вам упражнение для разъяснения. На поверхности, две интерпретации кажутся разумными:
Если это упражнение, и у вас есть оригинальная формулировка, вы можете указать цитату, но, как указано, ответ просто не ясен. Если домашняя работа, вы всегда можете предоставить два DFA, по одному для каждой интерпретации, с некоторым обсуждением двусмысленности.
Если речь идет только о вас, вы должны будете сами ответить, хотите ли вы пустую строку на своем языке.
Но ε - это своего рода гипотетическое мышление таким образом, что оно не содержит ничего, и есть только один способ начать и кончить зря. – Hailey
Можете ли вы сосредоточиться на вышеупомянутом комментарии? – Hailey
@Hailey Могут быть другие способы задуматься над вопросом, но есть хотя бы одна интерпретация, где пустая строка находится на языке и, по крайней мере, одна интерпретация, где это не так. Интерпретации значения пустой строки можно рассматривать как часть интерпретации вопроса. Я не уверен, что мне нужно добавить больше. – Patrick87
Это точное описание языка, который должен быть принят DFA? Я бы интерпретировал второе условие как «первый символ строки такой же, как и последний символ», что подчеркивает, что строка должна содержать символ, поэтому она не может быть пустой. – werkritter
Да, это точное описание языка. – Hailey
Итак, должен ли я отметить начальное состояние окончательным? – Hailey