构造上下文无关的语法 [英] Construct Context free Grammar

问题描述

如何为以下语言构建上下文无关的语法：

How can I construct a context free grammar for the following language:

L = {a^l b^m c^n d^p   | l+n==m+p; l,m,n,p >=1}

我首先尝试：

S -> abcd | aAbBcd | abcCdD | aAbcdD | AabBcCd

，然后 A =其他。 ..但我无法正常工作。

and then A = something else... but I couldn't get this working.

。

我想知道如何记住否，增加了许多c的要求。 b的增加？

例如：

I was wondering how can we remember how many c's shud be increased for the no. of b's increased?
For example:

string : abbccd

推荐答案

语法为：

1. S1 -> a S1 d | S2

1. S1 -> a S1 d | S2

S2 -> S3 S4

S3 -> a S3 b | epsilon

S3 -> a S3 b | epsilon

S4 -> S5 S6

S5 -> b S5 c | epsilon

S5 -> b S5 c | epsilon

S6 -> c S6 d | epsilon

S6 -> c S6 d | epsilon

第1条规则将a和d的数目相等。

Rule 1 adds equal number of a's and d's.

第3条规则将a和b的数目相等。

Rule 3 adds equal number of a's and b's.

第5条规则将b和c的数目相等。

Rule 5 adds equal number of b's and c's.

规则6将c和d的数目相等。

Rule 6 adds equal number of c's and d's

规则还确保根据给定的语言保持字母的顺序。

The rules also ensure that the ordering of the alphabets are maintained according to the language given.

这篇关于构造上下文无关的语法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！