Является ли регулярный язык всегда бесконечным

Меня немного смущает концепция обычного языка. Поскольку весь обычный язык может быть принят dfa, а в dfa всегда есть циклы. Таким образом, кажется, что dfa может принимать бесконечное количество строк. Означает ли это, что все обычные языки бесконечны? Что уж говорить о пустом множестве. Это обычный язык?


dfa regular-language
person flint_stone    schedule 22.02.2012    source источник
comment
Принял ли DFA строку или нет, зависит от того, оказались ли вы в состоянии принятия или нет. Довольно легко составить тривиальный DFA, который принимает ровно одну строку.   -  person Oliver Charlesworth    schedule 22.02.2012

Ответы (2)


arrow_upward
4
arrow_downward

определение обычного языка включает пустой набор. Он также включает одноэлементный язык {a}, так что нет, не все обычные языки бесконечны.

person Carl Norum    schedule 22.02.2012

arrow_upward
0
arrow_downward

Нет, не во всех DFA есть циклы. Регулярный язык — это тот, который может быть принят регулярным выражением (с использованием математического определения, а не определения pcre), и, например, «a» — это регулярное выражение, которое соответствует только точной строке «a». Итак, {a} — это обычный язык. :)

DFA для этого языка:

        a
START ----> ACCEPT
person bucko    schedule 22.02.2012