时间戳

首页 > 解决方案 > 正则表达式到上下文无关语法

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

问题描述

这个 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)*

标签： computation-theory

解决方案

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

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

片刻的反思应该让你相信正确的生产是

s10->s9s8

推荐阅读