Являются ли эти два обычных языка одинаковыми?

Question

Учитывая алфавит {a, b} где Na обозначает число вхождений a и Nb число вхождений в b:

1. L1 = {xy | Na(x) = Nb(y)}
2. L2 = {w | Na(w) and Nb(w) are even number}

Не был бы один DFA с четырьмя состояниями и использование мода могут принимать оба языка?

Answer 1

No, потому что оба языка разные, поэтому вы не можете рисовать один DFA для обоих языков.

Автомат однозначно определил язык, но да, конечно, для языка возможно использование более чем одного автоматов под названием «эквивалентные автоматы».

Язык L1 = A = {xy | Na(x) = Nb(y)} - это обычный язык. Регулярное выражение для этого языка:

(a + b)*a(a + b)*b(a + b)* +^

Чтобы понять этот язык и регулярное выражение для чтения: "Show that the following set over {a, b} is regular".

Язык L2 = A = {w | Na(w) and Nb(w) are even number} также является обычным языком. Регулярное выражение для этого языка:

((a + b(aa)*ab)(bb)*(ba(aa)*ab(bb)*)*a + (b + a(bb)*ba)(aa)*(ab(bb)*ba(aa)*)*b)* 

Чтобы понять этот язык и регулярное выражение для чтения: "Need Regular Expression for Finite Automata".

Но оба языка не равны, потому что на языке L1 есть некоторые строки, которые не принадлежат языку L2, например. ab - это строка в L1, но не состоит из четного числа a и b, следовательно, не относится к языку L2.

Примечание: Язык L2 либо не является подмножество языка L1, так как в L2 а строки четной длины и одного символа возможны как aa, aaaa, bb, bbbb, но эти строки не состоят в L1.

Оба языка отличаются друг от друга, поэтому один DFA является не возможно для обоих языков.