Регулярный язык всегда бесконечен

Question

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

Answer 1

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

Answer 2

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

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

        a
START ----> ACCEPT