构造产生如下语言的上下文无关文法各一个:{a^nb^m|m>=0,n>=0,且3n>=m>=2n}
时间: 2023-05-28 17:06:37 浏览: 46
文法1:
S -> aSbbb | E
E -> Eb | F
F -> aFb | G
G -> aGbb | H
H -> aHbbb | I
I -> aIbbbb | J
J -> aJbbbb | K
K -> aKbbbb | L
L -> aLbbbb | M
M -> aMbbbb | N
N -> aNbbbb | O
O -> aObb | P
P -> aPb | Q
Q -> aQbb | R
R -> aRbbbb | T
T -> aTbbb | U
U -> aUbb | V
V -> aV | ε
文法2:
S -> aSbbb | E
E -> Eb | F
F -> aFb | G
G -> aGbb | H
H -> aHbbb | I
I -> aIbbbb | J
J -> aJbbbb | K
K -> aKbbbb | L
L -> aLbbbb | M
M -> aMbbbb | N
N -> aNbbbb | O
O -> aObb | P
P -> aPb | Q
Q -> aQbb | R
R -> aRbbbb | T
T -> aTbbb | U
U -> aUbb | V
V -> aVbb | W
W -> aW | ε
相关问题
构造产生如下语言的上下文无关文法各一个:{a^mb^n|m>=n>=0}
S → AB | ε
A → aA | a
B → bB | b
解释:
- S是起始符号。
- A表示字符串中a的个数,B表示字符串中b的个数。
- ε表示空串。
- 产生式S → AB表示生成的字符串中a的个数大于等于b的个数。
- 产生式S → ε表示生成的字符串中只有b或者没有a和b。
{a^n b^n c^m d^m|n>=1,m>=1}U{a^n b^m c^m d^n|n>=1,m>=1}构造上下文无关文法
好的,我可以回答这个问题。以下是该语言的上下文无关文法:
S -> AB | CD
A -> aAb | ab
B -> cBd | cd
C -> aCd | ac
D -> bDd | bd
其中,S是起始符号,A和B生成第一个集合,C和D生成第二个集合。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)