Регулярное выражение в теории автоматов?

У меня есть следующий язык и его регулярное выражение

{w ∈ {a, b}* : w имеет префикс bab и суффикс babaa}

Ответ:

Регулярное выражение = bab(a ∪ b)*babaa ∪ babaa ∪ bababaa

Зачем нужен жирный шрифт?


dfa regular-language automata-theory
person Square-root    schedule 24.05.2017    source источник
comment
Считаете ли вы, что эти строки являются частью языка, и считаете ли вы, что первая часть регулярного выражения их принимает?   -  person Josh Lee    schedule 24.05.2017
comment
да первая часть определенно часть языка.. вторая часть не похожа на префикс или суффикс   -  person Square-root    schedule 24.05.2017
comment
хотя это правильный ответ. часть ответа подтверждает, что префикс и суффикс могут перекрываться. я до сих пор не понимаю   -  person Square-root    schedule 24.05.2017

Ответы (1)


arrow_upward
1
arrow_downward

баб — это префикс слова бабаа, а бабаа, очевидно, является суффиксом самого себя. Таким образом, babaa является возможной строкой.

бабаа — это суффикс бабабаа, а баб — префикс бабабаа. Значит, его тоже нужно включить.

person Community    schedule 24.05.2017