обычные языки с объединениями

Question

обычные языки закрыты для операции:

init (L) = набор строк w, такой что для некоторого x, wx находится в L.

EDIT: x canбыть любой строкой, символом или пустой строкой. Как я могу это доказать?

Answer 1

ОК, неправильно прочитал вопрос в первый раз, теперь я понял. Это все еще тривиально. Если посмотреть на то, что вы ищете, это разделить автоматизацию на два набора состояний S1 и S2, так что между ними только один переход (и если его из S1-> S2, S1 содержит, конечно, начальный узел, а S2 - конец узел). Такие существуют всегда (за исключением пустого языка), если такого узла нет, вы можете добавить его, поэтому w - это просто набор, содержащий пустое слово, что, конечно, также регулярно (как и случай с пустым языком).

Answer 2

Я думаю, что это новый DFA B, который превращает все состояние A (исходное DFA), которое может достичь конечных состояний A, в конечное состояние B.

Answer 3

Язык является регулярным, если есть конечный автомат, который распознает его. Итак, предположим, что L - регулярный язык, и пусть A - автомат, который его распознает. Теперь, скажем, что состояние A является «хорошим», если есть некоторый набор возможных переходов, начинающихся там и заканчивающихся в состоянии «принять». Определите новый автомат A ', в котором все переходы в "хорошие" состояния заменяются прямыми переходами в состояние принятия. Тогда язык, распознаваемый A ', является в точности init (L).

Answer 4

Если я не понимаю, ответ таков, что вы не можете.Потому что это неправда.

Сначала давайте рассмотрим язык L = {aa, bb, cc} и алфавит {a, b, c}

Итак, init(L) = {a, b, c}.Однако каждый из элементов в init(L) не входит в L.

Редактировать: Если мы объединяем пустые символы, то init(L) = {a, b, c, aa, bb, cc}.Который все еще не равен L.