语法G生成语言L的定义如下:
G=( {x,y},{S,A,B,C},P,S)
如果P的元素是:
S -> ABA
AB -> AC
CB ->英国广播公司
CA -> BBA
A -> a=E
B -> b
由G生成的L语言是否最准确地说是:
A.乔姆斯基0型
B. Chomsky类型1(对上下文敏感)
C. Chomsky类型2(无上下文)
D.乔姆斯基第3型(常规)
E.上述任何一项
我认为这是类型0,因为它对上下文不敏感。但我想知道,这些规则可能会被简化为其他规则,而变得对上下文敏感或上下文无关等等。如何处理这类问题?
语法G的定义如下:
G= ({a,b},{S,A,B},P,S)
其中P是集合:
S -> AB _ AS
一个-> a\\ aA
B- -> b-b- bb
由G生成的L语言是否最准确地说是:
A.乔姆斯基0型
B. Chomsky类型1(对上下文敏感)
C. Chomsky类型2(无上下文)
D.乔姆斯基第3型(常规)
E.上述任何一项
我认为这是免费的,因为LHS有一个非终端。但我不确定,因为这个规则可能会减少,成为正规的语法。
发布于 2018-07-23 06:12:26
语法1和编写的语法一样是上下文敏感的(不确定为什么您认为它不敏感,因为它与形式定义毫不含糊地匹配)。语法2与所写的上下文无关.
语法1的语言看起来是(a|E)b^k(a|E)
,其中k是2^i的形式,i是一个非负整数。这种语言似乎对上下文敏感。
语法2的语言看起来是aa*(b|bb)
,这是规则的。
因为问题是关于语言的,而不是写的语法,所以我想说,1是上下文敏感的,2是规则的。
https://stackoverflow.com/questions/51453288
复制