Во-первых, примечание о терминологии: язык - это набор строк в некотором алфавите. DFA и NFA распознают обычные языки , а не регулярные выражения . Может быть несколько регулярных выражений, которые определяют один и тот же язык. Для двух языков L1 и L2, если каждый член L1 является членом L2, и наоборот, L1 и L2 эквивалентны.
Что касается вашего первого вопроса, язык L1 состоит из всех строк по {a, b} с не менее двумя 'b's. Язык L2 состоит из всех строк над {a, b} с в точности двумя 'b's.
Строка "abbb" является элементом L1 и L3, но не L2. Так что оставляет L1 и L3
сравнивать. Любой элемент S из L1 должен содержать как минимум два символа «b». Пусть первые два "б"
в S соответствуют двум явным 'b' в выражении E3; тогда другие компоненты a*, a* и (a+b)* всегда могут быть сопоставлены, и S должно быть в L3. Следовательно, L1 является подмножеством L3.
Точно так же любой элемент S в L3 должен содержать по крайней мере два 'b'. Пусть они совпадают с двумя явными 'b' в выражении E1; другие компоненты (a+b)*, (a+b)* и (a+b)* также будут
есть совпадения, и S тоже в L1. Таким образом, L1 является подмножеством L3, а L3 является подмножеством L1, поэтому
L1 и L3 должны быть эквивалентны.
По поводу вашего второго вопроса: используйте насосную лемму . Предположим, у вас есть DFA, который принял этот язык ... покажите, что он также должен принимать строки не на этом языке, поэтому такой DFA не может существовать. Пусть S будет любой строкой в языке ... любая подстрока в S будет иметь либо все a, либо все b, либо оба ... так что произойдет после того, как вы "накачаете" ее?