正则表达式到上下文无关语法

Question

这个CFG看起来对吗？我正在为此RE构建CFG：(a U b(*U ab(a U b(*

this is the CFG:
s1->a
s2->b 

这是第一个(a U b(*

s3->s1|s2        (a U b)
s4->s3s4|E       (a U b)*

这是给中间的ab的

s5->a
s6->b

这是针对中间中的第二个(a、U、b(和(ab(

s7->s1|s2         (a U b) 
s8->s7s8|E        (a U b)* 
s9->s5s6          (ab)

ab与第二个(a U b(*相连

s10->s8s9         (ab(a U b)*)

这是最终的cfg

s11->s4|s10       (a U b)* U ab(a U b)*

Answer 1

除了这个之外，整个事情看起来都是正确的：

s10->s8s9         (ab(a U b)*)

片刻的思考应该会让你相信正确的产品是

s10->s9s8