Теория вычислений - показывает, что язык является регулярным

Question

Я просматриваю некоторые заметки к своему курсу по теории вычислений, и я немного застрял при показе следующего утверждения, и я надеялся, что кто-нибудь сможет мне помочь с объяснением:)

Пусть A - обычный язык. Язык B = {ab | a существует в A, а b не существует в A *} Почему B обычный язык?

Некоторые моменты для меня очевидны. Если b просто постоянная строка, это тривиально. Поскольку мы знаем, что a находится в A, а b - строка, обычные языки закрыты при объединении, поэтому объединение языка, который принимает эти две строки, очевидно, регулярно. Я не уверен, что b является постоянным, однако. Может быть, и если да, то это не проблема. Мне трудно понять это. Спасибо!

Answer 1

Вы можете доказать по построению: дайте регулярное выражение, которое распознает B. Класс регулярных языков закрыт при объединении, объединении, звездочке и дополнении.

Answer 2

В вопросе a и b речь идет не о константных строках, а о любых строках, а B - это язык строк с началом строки в A и концом строки не в A. Теперь, так как любой регулярный язык может распознаваться регулярным выражением, если Ra является регулярным выражением для распознавания языка A, то Ra, объединенное с регулярным выражением «not Ra», является регулярным выражением для распознавания языка B. B можно узнать по регулярному выражению, это обычный язык.

Edit: я изначально пропустил звезду после A в конце определения B в вопросе. Чтобы учесть это, включите в регулярное выражение, которое распознает b, также звезду.

Answer 3

B является обычным языком, потому что это язык, который заканчивается, когда появляется ввод "b". мы можем написать регулярное выражение для данного языка B как a * b