Если мы знаем, что CFG генерирует только обычный язык, можем ли мы получить соответствующее регулярное выражение?

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

Но если данная грамматика является контекстно-свободной грамматикой (но она порождает только регулярный язык), например

  • S->aAb
  • A->bB
  • B->cB|d
  • Is существует ли какой-либо существующий алгоритм, который вообще может получить регулярное выражение?

    Спасибо!

    9
    задан JackWM 16 May 2012 в 02:17
    поделиться