적어도 하나의 Kleene 별이있는 문맥없는 문법

Question

적어도 하나의 Kleene 별이있는 {a, b}를 통해 모든 정규 표현식을 생성하는 문맥 자유 문법을 만들려고합니다.

S ::= A + S | A 
A ::= B . A | B 
B ::= T | B* | (S) 
T ::= a | b | eps 

나는이 모든 정규 표현식을 생성 할 수 있다고 생각하지만, 내가 주위에 내 머리를 얻을 수없는 것은 적어도 하나 149) 클린의 별 (Kleene star가 필요 있도록를 정의하는 방법입니다 : 내가 지금까지했던 것은 이것이다 그 표현에 있어야합니다.

Answer 1

이 문제는 초기 상태 및 "통과"상태 인 상태 시스템의 일반적인 문제입니다. 해결책은 각각의 상태에 대응하는 우측을 갖는 것이다. 나는 통과 상태를 나타내는 규칙에 2를 사용할 것입니다.

S ::= S2 

S2 ::= A + S2 | A2 + S1 | A2 
A2 ::= B2 . A | B . A2 | B2 
B2 ::= B* | (S2) 

S1 ::= A + S1 | A 
A ::= B . A | B 
B ::= T | B* | (S1) 
T ::= a | b | eps 

전달 표현식은 전달 서브 표현식의 관점에서 정의됩니다. 따라서 문법은 항상 표현식의 왼쪽 또는 오른쪽에 클로저를 생성합니다.