171
правка
Изменения
Новая страница: «== Пустота == '''Пустота''' [[Регулярные языки: два определения и их эквивалентность|регулярно...»
== Пустота ==
'''Пустота''' [[Регулярные языки: два определения и их эквивалентность|регулярного языка]] — свойство языка не содержать ни одного слова. Язык, содержащий хотя бы одно слово, назовём '''непустым'''.
{{Утверждение
|id=
regEmpty
|statement=
Регулярный язык является непустым тогда и только тогда, когда в любом соответствующем ему автомате существует путь из стартового состояния в какое-либо из терминальных.
|proof=
Пусть язык содержит слово <tex>w</tex>. Любой автомат <tex>A</tex>, соответствующий этому языку, должен допускать <tex>w</tex>. Тогда при переходе из стартового состояния <tex>A</tex> по символам <tex>w</tex> получится путь, оканчивающийся в одной из терминальных вершин.
Пусть в автомате существует путь из стартового состояния в одно из допускающих. Рассмотрим последовательность символов на рёбрах, образующих этот путь. Строка из этой последовательности допускается автоматом, а значит, принадлежит языку.
}}
=== Алгоритм проверки языка на пустоту ===
Для определения пустоты языка по соответствующему ему автомату проще всего использовать алгоритм [[Обход в глубину, цвета вершин|обхода в глубину]]. Язык не является пустым тогда и только тогда, когда при поиске из стартового состояния автомата окажется достижимой хотя бы одна терминальная вершина.
boolean dfs(State v) {
v.seen = true;
if (v.isFinal) {
return false;
}
for (State u : v.next) {
if (!u.seen && !dfs(u)) {
return false;
}
}
return true;
}
boolean isEmpty(Automaton a) {
for (State v : a) {
v.seen = false;
}
return dfs(a.start);
}
'''Пустота''' [[Регулярные языки: два определения и их эквивалентность|регулярного языка]] — свойство языка не содержать ни одного слова. Язык, содержащий хотя бы одно слово, назовём '''непустым'''.
{{Утверждение
|id=
regEmpty
|statement=
Регулярный язык является непустым тогда и только тогда, когда в любом соответствующем ему автомате существует путь из стартового состояния в какое-либо из терминальных.
|proof=
Пусть язык содержит слово <tex>w</tex>. Любой автомат <tex>A</tex>, соответствующий этому языку, должен допускать <tex>w</tex>. Тогда при переходе из стартового состояния <tex>A</tex> по символам <tex>w</tex> получится путь, оканчивающийся в одной из терминальных вершин.
Пусть в автомате существует путь из стартового состояния в одно из допускающих. Рассмотрим последовательность символов на рёбрах, образующих этот путь. Строка из этой последовательности допускается автоматом, а значит, принадлежит языку.
}}
=== Алгоритм проверки языка на пустоту ===
Для определения пустоты языка по соответствующему ему автомату проще всего использовать алгоритм [[Обход в глубину, цвета вершин|обхода в глубину]]. Язык не является пустым тогда и только тогда, когда при поиске из стартового состояния автомата окажется достижимой хотя бы одна терминальная вершина.
boolean dfs(State v) {
v.seen = true;
if (v.isFinal) {
return false;
}
for (State u : v.next) {
if (!u.seen && !dfs(u)) {
return false;
}
}
return true;
}
boolean isEmpty(Automaton a) {
for (State v : a) {
v.seen = false;
}
return dfs(a.start);
}
