设有文法G[N]: N→D|ND D→0|1|2|3|4|5|6|7|8|9 (2)给出句子0123和268的最左推导和最右推导。 (1)G[N]定义的语言是什么?
时间: 2024-06-15 14:08:33 浏览: 18
根据文法G[N]的定义,语言L(G[N])是由非终结符N生成的所有字符串的集合。在这个文法中,非终结符N可以生成一个数字D,或者由一个数字D后面跟着另一个非终结符N生成的字符串。
所以,语言L(G[N])包含了所有由数字0到9组成的字符串。
对于问题(2),我们需要找出句子0123和268的最左推导和最右推导。
最左推导是从左到右选择最左边的非终结符进行替换,直到得到目标句子。最右推导则是从右到左选择最右边的非终结符进行替换。
对于句子0123:
最左推导:
N → ND → DND → 0ND → 01D → 012D → 0123
最右推导:
N → ND → N3D → N23D → N123D → N0123 → 0123
对于句子268:
最左推导:
N → ND → N6D → N26D → N268D → 268
最右推导:
N → ND → N8D → N68D → N268D → 268
相关问题
算法G[N]为: N→D|ND D→0|1|2|3|4|5|6|7|8|9 改造该文法,使其产生正整数
要改造该文法使其产生正整数,可以通过以下方式进行修改:
1. 将非终结符N的产生式改为N→D|ND,表示N可以由一个数字D或者一个数字D后跟一个N生成。
2. 将终结符D的产生式改为D→1|2|3|4|5|6|7|8|9,表示D可以是数字1到9中的任意一个。
修改后的文法如下:
G[N]为: N→D|ND
D→1|2|3|4|5|6|7|8|9
这样修改后的文法可以生成正整数。例如,根据该文法,可以生成以下正整数:
1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, ...
令文法G为 N→D | ND D→0 | 1 | 2 | 3 | 4 | 5 | 6| 7 | 8 | 9 给出句子0127、34和568的最左推导和最右推导。
根据题目描述,文法G为:
N → D | ND
D → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
该文法的语言是由0-9组成的所有字符串。
对于句子0127,最左推导和最右推导如下:
最左推导:
N → ND → NDD → 0DD → 01D → 012
最右推导:
N → ND → NDD → ND7 → N127 → D0127 → 0127
对于句子34,最左推导和最右推导如下:
最左推导:
N → ND → 3D → 34
最右推导:
N → ND → 34D → 34
对于句子568,最左推导和最右推导如下:
最左推导:
N → ND → ND8 → N568 → D568
最右推导:
N → ND → N8D → 5D → 56D → 568