Учитывая алфавит {a, b}, мы определяем Na(w) как количество вхождений a в слово w и аналогично для Nb(w). Покажите, что следующий набор над {a, b} регулярен.
A = {xy | Na(x) = Nb(y)}
Мне трудно понять, с чего начать решение этой проблемы. Любая информация будет глубоко цениться.
Да это обычный язык!
Любая строка состоит, если a и b принадлежат языку A = {xy | Na(x) = Nb(y)}.
Пример:
Предположим, что строка: w = aaaab, мы можем разделить эту строку на префикс x и суффикс y.
w = a aaab
--- -----
x y
Количество a в x равно единице, и количество b в y также равно единице.
Аналогично строке типа: abaabaa можно разбить на x = ab (Na(x) = 1) и y = aabaa (Nb(y) = 1).
Или w = bbbabbba как x = bbbabb (Na(x) = 1) и y = ba (Nb(y) = 1)
Или w = baabaab, поскольку x = baa и y = baab с (Na(x) = 2) и (Nb(y) = 2).
Таким образом, вы всегда можете разбить строку, состоящую из a и b, на префикс x и суффикс y так, чтобы Na(x) = (Nb(y).
Официальная проверка:
Примечание. Строки состоят только из as или состоят из bs, не относятся к языку, например. aa, a, bbb...
Определим новый Лагранж CA таким образом, что CA = {xy | Na(x) != Nb(y)}. CA означает дополнение A состоит из строки, состоящей только из as или только из bs.
1А CA — это обычный язык, его регулярное выражение — a+ + b+.
Теперь, когда мы знаем, что CA является обычным языком (это может быть выражение с помощью регулярного выражения и, таким образом, DFA), а дополнение любого регулярного языка является регулярным, следовательно, язык A также является обычным языком!
Чтобы построить DFA для дополнительного языка, см.: Поиск дополнения DFA? и чтобы написать регулярное выражение для DFA, используйте следующие два метода.
"+" Оператор в регулярном выражении в официальные языки
PS: Кстати, регулярное выражение для A = {xy | Na(x) = Nb(y)} равно (a + b)*a(a + b)*b(a + b)*.
Сначала выясним, как доказать регулярность множества. Один из способов — определить конечный автомат, который принимает язык.
Второе: может подумать, почему набор не регулярный.
maybe think about why the set is not regular. неправильно доказывать, что определенный язык не является регулярным, у нас есть свойство леммы накачки регулярного языка, но доказательство регулярности языка довольно запутанно, потому что это необходимое, но недостаточное условие.
- person Grijesh Chauhan; 28.09.2013
Подсказка: A = {a, b}*.
Попробуйте доказать это индукцией по длине слова или нахождением кратчайшего слова не в A.
