瞭解CFG的基本知識

Question

在Sipser的書中剛剛開始關於CFL的章節，並且已經不瞭解基礎知識。

讓這成爲一些語言的語法：

S -> A0A 
A -> 00A | 11A | 10A | 01A | e 

我真搞不清楚這個A0A部分。這是否意味着從0開始的左手側應始終與右手側相同。這是否意味着00011或000不是用這種語言呢？

Answer 1

任何S是您對任何A的任何選項，其後是單個文字0，然後是另一個選項A。每個A是獨立的。

字符串00011是在語言，因爲你可以選擇你的兩個A S（例如），使得第一個是00A，第二個是11A。如果遞歸地選取空字符串（e）作爲「剩餘」A的兩個字符串，那麼當您連接所有內容時，最終將以字符串00011結尾。

你可以做類似的事情來獲得字符串000。

Answer 2

A轉換爲空或兩個二進制數字，然後轉換爲A.這意味着A轉換爲偶數個二進制數字的任意序列。

S轉換爲A，然後是0，然後是A.這意味着S轉換爲偶數個二進制數字，然後是0，然後是偶數個二進制數字。也就是說，S是中間有0的奇數個二進制數字序列。

這是否意味着從0開始的左手側應始終與右手側相同。

不，爲什麼？兩個不同的A可以轉換成不同的序列。