Меня немного смущает концепция обычного языка. Поскольку весь обычный язык может быть принят dfa, а в dfa всегда есть циклы. Таким образом, кажется, что dfa может принимать бесконечное количество строк. Означает ли это, что все обычные языки бесконечны? Что уж говорить о пустом множестве. Это обычный язык?
Является ли регулярный язык всегда бесконечным
comment
Принял ли DFA строку или нет, зависит от того, оказались ли вы в состоянии принятия или нет. Довольно легко составить тривиальный DFA, который принимает ровно одну строку.
- person Oliver Charlesworth   schedule 22.02.2012
Ответы (2)
определение обычного языка включает пустой набор. Он также включает одноэлементный язык {a}
, так что нет, не все обычные языки бесконечны.
person
Carl Norum
schedule
22.02.2012
Нет, не во всех DFA есть циклы. Регулярный язык — это тот, который может быть принят регулярным выражением (с использованием математического определения, а не определения pcre), и, например, «a» — это регулярное выражение, которое соответствует только точной строке «a». Итак, {a} — это обычный язык. :)
DFA для этого языка:
a
START ----> ACCEPT
person
bucko
schedule
22.02.2012