這是一種上下文無關的語言嗎？

Question

這是語言

L = {a^i b^j a^i b^k | i, j, k >= 0} 

然後，我可以嘗試語法這個語言：

S -> ABCD 
A -> a | aA | lambda 
B -> b | bB | lambda 
C -> a | aC | lambda 
D -> b | bD | lambda 

它是免費的情況下，...是正確的語法？

Answer 1

你的語法允許aaba，它不應該，因爲應該始終是偶數的a S：

ABCD 
aABCD 
aaBCD 
aabCD 
aabaD 
aaba 

一個正確的答案應該是：

Start → A B 

A → a A a | B 
B → bB | ε 

• B生成任何數量的b s（包括none）。
• A是a的序列，隨後B，隨後由相同數量的a