Linguaggi di programmazione: esercizio 2 grammatica

Dato il linguaggio

L = {0ⁿ 1^m 2^k | n = m  and  m = k}

definire la grammatica.

N.B. n = m and m = k significa semplicemente che n = m = k, quindi:

 

G = (X,V,S,P)

X = (0,1,2)

V = (S, A, B, C)

 

P = {

S => λ | SABC | ABC

A => 0

B => 1

C => 2

20 => 02

10 => 01

21 => 12

}

 

oppure

P = {

S => λ | 0SBC | 0BC

0B => 01

1B => 11

1C => 12

2C => 22

CB => BC

}

 

Entrambe le grammatiche sono di tipo 0 (Macchina di Turing)