정규 표현식을 오른쪽 선형 정규 문법으로 변환하기위한 알고리즘

Question

정규 표현식을 오른쪽 선형 문법으로 변환하는 알고리즘이 있습니까? 나는 간단한 정규 표현식을 CFG로 변환하는 알고리즘에 익숙하다. 오른쪽 선형 문법에는 더 엄격한 규칙이 있습니다. A -> a B 또는 A -> a. 이로 인해 알고리즘을 구성하는 것이 어려워집니다.

Answer 1

비 결정적-유한 오토마타 (NFA) [1][2][3]
또한 마우스 오른쪽 LINNER - 문법 (RLG)에 DFA를 변환하는 alogorithims 거기에 정규 표현식 (RE)를 변환하는 알고리즘 방법이 있습니다. [1][2]

물론 RE는 RL을 RLG로 변환하는 알고리즘 방식입니다.

난 당신이이 Constructing an equivalent Regular Grammar from a Regular Expression