设计一个 PDA 来识别这种语言

问题

生成识别 E={aibj| i 不等于 j 且 I 不等于 2j} 语言的下推自动机 (PDA)。

解决方案

考虑如下图所示的两种语言 −

L1={aibj|i,j>=0 且 i>2j}L2={aibj|i,j>=0 且 i<2j}

说服你自己 L=L1UL2

在 L1 中，a 的数量多于 b 的两倍，因此 L1 如下 −

   S1->aA

   A->aaAb|aA|epsilon

在 L2 中，a 的数量少于 b 的两倍

因此 L2 的 CFG 变成如下 −

   S2->Bb|aBb

   B->Bb|aBb|aaBb|epsilon

   S->S1|S2

L1: {aibj:i>2j}

L2:{aibj: i<2j}

Bhanu Priya

更新于: 2021 年 6 月 16 日

484 次浏览

开启您的职业生涯

通过完成课程获得认证

开始