171
правка
Изменения
м
Язык {{Определение|id=finite|definition=[[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] называется '''конечным''', если принадлежащее ему множество слов конечно.}}
Нет описания правки
== Пустота ==
{{Определение|id=empty|definition=[[Регулярные языки: два определения и их эквивалентность|Регулярный язык]] является называется '''пустым''', если он не содержит ни одного слова. }} Язык, содержащий хотя бы одно слово, назовём '''непустым'''.
{{Утверждение
== Совпадение ==
{{Определение
|id=equal
|definition=
Два [[Регулярные языки: два определения и их эквивалентность|регулярных языка]] '''совпадают''', если любое слово или содержится в обоих языках, или не содержится ни в одном из них.
}}
Пусть <tex>A_{1}</tex> и <tex>A_{2}</tex> - детерминированные конечные автоматы, соответствующие языкам <tex>L_{1}</tex> и <tex>L_{2}</tex> над одним алфавитом <tex>\Sigma</tex>, соответственно. Совпадение языков на языке конечных автоматов (''эквивалентность'') означает, что любое слово, допустимое одним автоматом, допускается и другим. Назовём состояния <tex>p_{1} \in A_{1}</tex> и <tex>p_{2} \in A_{2}</tex> '''различимыми''', если существует строка <tex>w</tex> из символов <tex>\Sigma</tex>, для которой выполняется
== Включение ==
{{Определение|id=inclusion|definition=[[Регулярные языки: два определения и их эквивалентность|Регулярный язык ]] <tex>L_{1}</tex> '''входит (включается)''' в регулярный язык <tex>L_{2}</tex>, если любое слово, принадлежащее <tex>L_{1}</tex>, принадлежит <tex>L_{2}</tex>.}}
=== Алгоритм проверки на включение ===
== Конечность языка, подсчёт числа слов ==
{{Утверждение
