Путаница, связанная с контекстно-зависимой грамматикой

Я хочу знать, есть ли у меня следующее правило

AB -> BA.

Является ли это контекстно-зависимым?

Другое правило A -> aAB

Является ли это контекстно-зависимым.

Я думаю, что оба они не зависят от контекста. Любые идеи или рекомендации?


grammar context-free-grammar
person user34790    schedule 12.09.2012    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Обе грамматики не зависят от контекста. Но контекстно-свободные грамматики являются подмножеством контекстно-зависимых грамматик. (Грамматическая иерархия) Так что да, это контекстно-зависимые грамматики.

person HS Developer    schedule 12.09.2012
comment
Вы можете объяснить, почему они контекстно-зависимы? - person user34790; 12.09.2012
comment
правило для контекстно-зависимых: aAb -> aYb, где a и b могут быть пустыми, Y — строка терминалов и нетерминалов, поэтому AB -> BA удовлетворяет этому правилу, A и B — нетерминалы, A -> aAB, в данном В этом случае вы можете принять aAB за Y в правиле (aAb -> aYb и a,b пусты). надеюсь, это поможет - person HS Developer; 12.09.2012
comment
просто чтобы добавить вам ссылку, здесь легко понять: вики - person HS Developer; 12.09.2012
comment
как получилось, что AB->BA является контекстно-зависимым, я до сих пор не понимаю. Что вы подразумеваете под A и B -не терминалами, что такое a, A, b и Y в этом случае. - person user34790; 12.09.2012
comment
извините, это была моя вина. на самом деле AB-> BA не зависит от контекста, но A -> aAB зависит от контекста. нетерминальный символ, поскольку A, B означает, что он может перейти к нетерминальному или терминальному символу. терминал означает, что он не может перейти к другим символам, это конечное состояние. Y в этом правиле — это список терминалов и нетерминалов. Таким образом, у вас есть базовое правило aAb -> aYb, например: Xi -> HXi (и HXi -> HHXi), в этом случае X не является терминальным, как A в правиле, HX — результирующее слово Y. Таким образом, A -> aAB удовлетворяет правилу aAb -> aYb (a,b пусты и A -> Y, где Y = aAb, грамматик может быть A -> aAb -> aaAbb-> aaaAbbb) - person HS Developer; 12.09.2012
comment
Вы не можете найти такие a,b, A, Y, чтобы они соответствовали AB -> BA для вашего случая - person HS Developer; 12.09.2012