2024年3月14日发(作者:寿雅爱)
第
2
章习题解答
1.
文法
G[S]
为:
S->Ac|aB
A->ab
B->bc
写出
L(G[S])
的全部元素
[
答案
]
S=>Ac=>abc
或
S=>aB=>abc
所以
L(G[S])={abc}
2.
文法
G[N]
为:
N->D|ND
D->0|1|2|3|4|5|6|7|8|9
G[N]
的语言是什么?
[
答案
]
G[N]
的语言是
V
。
V={0,1,2,3,4,5,6,7,8,9}
N=>ND=> =>D=>D……D
3.
已知文法
G[S]
:
Sf dAB Af aA|a B|bB
问:相应的正规式是什么?
G[S]
能否改写成为等价的正规文法?
[
答案
]
正规式是
daa*b*
;
相应的正规文法为
(
由自动机化简来
)
:
G[S]:S
—
dA A
—
a|aB B
—
aB|a|b|bC C
—
bC|b
也可为
(
观察得来
):G[S]:S
—
dA A
—
a|aA|aB B
—
bB|
&
4.
已知文法
G[Z]
:
Z->aZb|ab
写出
L(G[Z])
的全部元素。
[
答案
]
Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbb
L(G[Z])={a b|n>=1}
nn
5.
给出语言
{abc
1
n>=1,m>=0}
的上下文无关文法。
nn
[
分析
]
本题难度不大,主要是考上下文无关文法的基本概念。 上下文无关文法的基 本
定义是:
A-> B ,A € Vn ,B€( VnU Vt)
*
,
注意关键问题是保证
a
n
b
n
的成立, 即“
a
与
b
的个数要相等”,为此,可以用一条形如
A->aAb|ab
的产生式即可解 决。
[
答案
]
构造上下文无关文法如下:
S->AB|A
A->aAb|ab
B->Bc|c
[
扩展
]
2024年3月14日发(作者:寿雅爱)
第
2
章习题解答
1.
文法
G[S]
为:
S->Ac|aB
A->ab
B->bc
写出
L(G[S])
的全部元素
[
答案
]
S=>Ac=>abc
或
S=>aB=>abc
所以
L(G[S])={abc}
2.
文法
G[N]
为:
N->D|ND
D->0|1|2|3|4|5|6|7|8|9
G[N]
的语言是什么?
[
答案
]
G[N]
的语言是
V
。
V={0,1,2,3,4,5,6,7,8,9}
N=>ND=> =>D=>D……D
3.
已知文法
G[S]
:
Sf dAB Af aA|a B|bB
问:相应的正规式是什么?
G[S]
能否改写成为等价的正规文法?
[
答案
]
正规式是
daa*b*
;
相应的正规文法为
(
由自动机化简来
)
:
G[S]:S
—
dA A
—
a|aB B
—
aB|a|b|bC C
—
bC|b
也可为
(
观察得来
):G[S]:S
—
dA A
—
a|aA|aB B
—
bB|
&
4.
已知文法
G[Z]
:
Z->aZb|ab
写出
L(G[Z])
的全部元素。
[
答案
]
Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbb
L(G[Z])={a b|n>=1}
nn
5.
给出语言
{abc
1
n>=1,m>=0}
的上下文无关文法。
nn
[
分析
]
本题难度不大,主要是考上下文无关文法的基本概念。 上下文无关文法的基 本
定义是:
A-> B ,A € Vn ,B€( VnU Vt)
*
,
注意关键问题是保证
a
n
b
n
的成立, 即“
a
与
b
的个数要相等”,为此,可以用一条形如
A->aAb|ab
的产生式即可解 决。
[
答案
]
构造上下文无关文法如下:
S->AB|A
A->aAb|ab
B->Bc|c
[
扩展
]