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

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

Существует ли строка abaabbabbabaab в S*?

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

  1. (абааб) (баб) (б) (а) (а) (б)
  2. (абааб) (баб) (б) (аа) (б)
  3. (абааб) (баб) (ба) (аб)
  4. (абааб) (баб) (баа) (б)
  5. (абааб) (баб) (б) (ааб)

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

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

  • Это правильный способ факторизации (токенизации) строки?

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

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

tokenize automata-theory
person For4 Waste    schedule 28.06.2018    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

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

person Peter Leupold    schedule 02.07.2018
comment
Существует ли строка abaabbabbabaab в S*? это означает, что я учел эту строку, а не алфавит. Вы можете увидеть эту строку, а затем коэффициенты, которые я сделал. - person For4 Waste; 03.07.2018
comment
Строка $abaabbabbaab$ не находится в $S^*$. Все ваши факторизации включают факторы, не принадлежащие $S$. Просто посмотрите на правый конец строки. Ни одна из пяти строк из $S$ не является суффиксом строки; таким образом, ясно, что его нельзя факторизовать. - person Peter Leupold; 04.07.2018