^^Formal grammar. es

Grammatica formale per le espressioni di operazioni binarie.

Formal grammar. es lingua naturale.

Example of formal grammar

Σ = {a, b, c} the alphabet

S                  the start symbol

1. S → aSb    the production rules
2. S → c

we start with S, and can choose a rule to apply to it.

  1. If we choose rule 2, we obtain the string c, and we are done.
  2. If we choose rule 1, we obtain the string aSb;
    1. if we then choose rule 1 again, we replace S with aSb and obtain the string aaSbb;
    2. if we now choose rule 2, we replace S with c and obtain the string aacbb, and are done.

      We can write this series of choices more briefly, using symbols:

      S ⇒ aSb ⇒ aaSbb ⇒ aacbb.

The language of the grammar is then the infinite set

{ancbn ∣ n ≥ 0} = {c, acb, aacbb, aaacbbb, …}

n in particular represents the nr of times production rule 1 has been applied.

 

2 grammar with same language

1. S → a
2. S → Sa        		1. S → a
2. S → SS        
producono le stesse stringhe

 

1. S → a
2. S → Sa        
S 1 a
S 2 Sa 1 aa
S 2 Sa 2 Saa 1 aaa
S 2 Sa 2 Saa 2 Saaa 1 aaaa 
S 2 Sa 2 Saa 2 Saaa 2 Saaaa 1 aaaaa
S 2 Sa 2 Saa 2 Saaa 2 Saaaa 2 Saaaaa 1 aaaaaa

 

tutte le produzioni di una stringa lunga fino a 3

1. S → a
2. S → SS        
S 1 a
S 2 SS 1 Sa  1 aa
             2 SSa 1 Saa 1 aaa
                   1 aSa 1 aaa
       1 aS  1 aa
             2 aSS 1 aSa 
                   1 aaS 1 aaa
       2 SSS 1 SSa 
             1 SaS 1 Saa
             1 SaS 1 aaS
             1 aSS

la stringa lunga 3 si puo' produrre in 10 modi diversi

 

Slight different L(anguage)

L1 L2
1. S → a
2. S → Sa        		1. S → ε   empty string
2. S → Sa

The language of the grammar is the infinite set

L1= {an ∣ n > 0} = {a, aa, aaa, …}

L2= {an ∣ n ≥ 0} = {ε, a, aa, aaa, …}

 

 

Talk

 

Dis .odg