Как факторизовать строку, чтобы проверить ее принадлежность к языку, который генерируется из алфавита?

Question

Пусть S = {a, bb, bab, abaab} - алфавит. а клини замыкание будет S *, будут все возможные комбинации.

Строка abaabbabbaab существует в S *?

Каков метод разложения на множители для проверки, находится ли он в S * или нет? Я сделал это следующими способами, Возможная факторизация:

1. (abaab) (баб) (б) (а) (а) (б)
2. (abaab) (баб) (б) (аа) (б)
3. (abaab) (баб) (ба) (AB)
4. (abaab) (баб) (БАД) (б)
5. (abaab) (баб) (б) (AAB)

мы можем видеть, что (abaab) (bab) совпадает, но более поздняя часть не совпадает с комбинациями воли в S *. Я разложил более позднюю часть во многих отношениях, но она все еще не совпадает Я хочу спросить это,

• это правильно?

• Является ли это правильным способом факторизации (токенизации) строки?

• все ли пары факторизации верны?

• - это правильный метод проверки строки на принадлежность язык или нет?

Answer 1

Некоторые из ваших факторизаций содержат $ (b) $, которого нет в $ S $. Так что они не верны.

Я думаю, что ваш метод является исчерпывающим методом проб и ошибок. Если вы делаете это правильно, это правильный способ найти факторизацию. Для проверки принадлежности к языку это работает, если язык задан в форме клиниевского замыкания конечного языка.