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

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

0 голосов
/ 22 февраля 2012

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

Ответы [ 2 ]

4 голосов
/ 22 февраля 2012

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

0 голосов
/ 22 февраля 2012

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

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

        a
START ----> ACCEPT
...