Как я могу получить эти грамматики

Question

      G = (V={S,X,Y}, T={0,1,2},P,S)

S -> 0X1
X ->S | 00S2 | Y | ε
Y ->X | 1

Проблема в том, что я не умею вычислять числа.

Как я могу вывести это здесь:00111 ∈ L(G)

И здесь я должен привести три вывода:0000121 ∈ L(G)

Answer 1

Чтобы сделать вывод, вы начинаете с начального символа (в данном случае), который является четвертым элементом в кортеже грамматики). Затем вы применяете производственные правила ( P) в любом порядке, который вам кажется подходящим.

Производство вроде:

      X → S | 00S2 | Y | ε

означает, что вы можете заменить X с участием

• S, или же
• 00S2, или же
• Y, или же
• ничего такого.

Другими словами, вы читаете производственные правила следующим образом:

• → означает «можно заменить на».
• | означает "или"
• ε означает «ничего» (замена символа ничем означает его удаление из текущей строки.)

Все остальное - всего лишь возможный символ в строке. Вы продолжаете выполнять замены по одной, пока не дойдете до строки, которую пытаетесь получить.

Вот краткий пример:

      S
 → 0X1      (using S → 0X1)
 → 000S21   (using X → 00S2)
 → 0000X121 (using S → 0X1)
 → 0000121  (using X → ε)

Вот и все. Вообще ничего сложного. Просто куча операций поиска и замены. (Вам не нужно заменять первое вхождение, если существует более одной возможности. Вы можете выполнять замены в любом порядке. Но удобно быть систематическим.)