Esercitazione settima

G = ( , , P, S }

P =

Poiché i valori di k, l ed 252b11c m non dovevano seguire uno schema preciso, è stata usata la funzione Randomize per avere valori variabili ;

Codifica in Pascal di una grammatica che generi stringhe del tipo a^lb^kc^k e del tipo a^kb^kc^l con valori di k, l ed m variabili tra 1 e 20. In particolare questa grammatica è del tipo :

G = ( , , P, S )

P =

Codifica in Pascal di una grammatica che generi stringhe del tipo aⁿbⁿcⁿ con n variabile fra 1 e 20 ; in particolare questa grammatica è del tipo :

G = ( , , P, S )

P=

Programma Grammatica a ^k b ^l c ^m ( VII )^nnnnmnnnnnnn

Program gram1 ;

uses crt ;

type vettore =array [ 1..63 ] of char ;

type vetbool = array [ 1..20 ] of boolean ;

var v, t ,y : vettore ;

var z : vetbool ;

var i, n, w, q, k, x : integer ;

const a = char ( ' a ' ) ;

const b = char ( ' b ' ) ;

const c = char ( ' c ' ) ;

const F = char ( ' A ' ) ;

const D = char ( ' B ' ) ;

const G = char ( ' C ' ) ;

const S = char ( ' S ' ) ;

Procedure produzione ( var v : vettore ; var k :integer ) ;

var i, n, z, w : integer ;

Begin

v [ 1 ] := S ;

if v [ 1 ] = S then begin

v [ 1 ] := F ;

v [ 2 ] := D ;

v [ 3 ] := G ;

end ;

n := Random ( 20 ) +1 ;

for i := 1 to n do begin

if i < > n then begin

if v [ i ] = F then begin

v [ i+3 ] := v [ i+2 ] ;

v [ i+2 ] := v [ i+1 ] ;

v [ i+1 ] := v [ i ] ;

v [ i ] := a ;

end ;

end

else if v [ i ] = F then v [ i ] := a ;

end ;

z := Random ( 20 ) +1 ;

for i :=  n+1 to n +z do begin

if i <> ( n + z ) then begin

if v [ i ] = D then begin

v [ i+2 ] := v [ i+1 ] ;

v [ i+1 ] := v [ i ] ;

v [ i ] := b ;

end ;

end

else if v [ i ] = D then v [ i ] := b ;

end ;

w := Random ( 20 ) +1 ;

for i := n + z + 1 to w + n + z do begin

if i <> ( w + n + z ) then begin

if v [ i ] = G then begin

v [ i+1 ] := v [ i ] ;

v [ i ] := c ;

end ;

end

else if v [ i ] = G then v [ i ] := c ;

end ;

k := w + n + z ;

for i := 1 to k do write ( v [ i ] ) ;

writeln

end

Function amb ( t, y :vettore): boolean ;

var i, c : integer ;

begin

c := 0 ;

for i := 1 to 59 do if t [ i ] = y [ i ] then c := c+1 ;

if c = 59 then amb := True else amb := False ;

end

Begin

v [ 1 ] := S ;

for i := 1 to 10 do begin

produzione ( v, k ) ;

for x := 1 to k do begin

t [ x ] := v [ x ] ;

write ( t [ x ] ) ;

end ;

writeln ( ' ) ;

produzione ( v, k ) ;

for x := 1 to k do begin

y [ x ] := v [ x ] ;

write ( y [ x ] ) ;

end ;

writeln (' ) ;

z [ i ] := amb ( t, y ) ;

i := i+1 ;

end;

for i:=1 to 20 do begin

if z[ i ] = true then writeln ( 'La grammatica è ambigua ' )

else writeln ( 'La grammatica non è ambigua' ) ;

end ;

readln

end

Dimostrazione pratica

Output :

abccccc

aaaaaaaaabbbbbbbc

aaaaaaabbbbbbbbbbc

aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbccccccccccccccc

aaaabbbbbbbbbbbbbbbbbbbcc

aaaaaaaaaaaaaaaaaabbbbbbbbbbbcccccccccccccccccccccccccccc

aaaaaaabbbbbbbbbbbbbbbbbbbbbbccccccccccccccc

abc

aaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbcc

aaaaaaabbbbbbbbbbbbbbbbbbbbbbccccccccccccccccccccccccccc

aaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbccccccccccc

aaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbcccccccccccccc

abbbbbbbbbbbbbbbbbbbbbbccccccccccccccccccccccccc

aaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbcccccccccccccccc

aaabbbc

aaaaaabc

aaaaaaaaaaaaaaaaabbbbbbbbbbbbbbccccc

aaaaaaaaaabbcccccccc

abbbbbbbbbccccccccccccccccccccccccccccccccccc

aaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbc

La grammatica non è ambigua

Programma Grammatica a^l b^k c^k ed a^k b^k c^l ( VI bis )

Program Gram2;

uses crt;

type vettore =array [1..59] of char ;

type vet =array [1..20] of boolean ;

var v1,v2,y,t : vettore ;

var x :vet ;

var i, z, q :integer ;

const a = char ( 'a' ) ;

const b = char ( 'b' ) ;

const c = char ( 'c' ) ;

const S = char ( 'S' ) ;

const F = char ( 'A' ) ;

const G = char ( 'C' ) ;

const D = char ( 'D' ) ;

const E = char ( 'E' ) ;

Procedure produzione1 ( n :integer ;var v :vettore ;var z :integer );

var i, q : integer ;

Begin

v1 [ 1 ] := F ;

v1 [ 2 ] := E ;

if n =1 then begin

if v1 [ n ]= F then v1 [ n ] :=a ;

if v1 [ n+1 ]= E then begin

v1 [ n+1 ] :=b ;

v1 [ n+2 ] :=c ;

end ;

end

else if n = 2 then begin

if v1 [ 1 ] = F then v1 [ 1 ] := a ;

if v1 [ 2 ] = E then begin

v1 [ n+2 ] := c ;

v1 [ n+1 ] := E ;

v1 [ n ] := b ;

end ;

for i:= 1 to 59 do begin

if v1 [ i ] = E then begin

v1 [ i+2 ] := v1 [ i+1 ] ;

v1 [ i+1 ] := c ;

v1 [ i ] := b ;

end ;

end;

end

else begin

for i := 1 to ( n-1 ) do begin

if i < > ( n-1 ) then begin

if v1 [ i ] = F then begin

v1 [ i+2 ] := v1 [ i+1 ] ;

v1 [ i+1 ] := v1 [ i ] ;

v1 [ i ] := a ;

end ;

end

else if v1 [ i ] = F then v1 [ i ] := a ;

end ;

q :=2 ;

for i := n to ( n+z ) do begin

if i <> ( n+z ) then begin

if v1 [ i ] = E then begin

if v1 [ i+1 ] = c then begin

v1 [ i+q ] := v1 [ i+1 ] ;

v1 [ i+q-1 ] := c ;

v1 [ i+1 ] := v1 [ i ] ;

v1 [ i ] := b ;

q := q+1 ;

end

else begin

v1 [ i+q ] := c ;

v1 [ i+1 ] := v1 [ i ] ;

v1 [ i ] := b ;

q := q+1 ;

end ;

end;

end

else begin

v1 [ i+q-1 ] := c ;

v1 [ i+1 ] := c ;

v1 [ i ] := b ;

q := q+1 ;

end ;

end ;

end ;

for i:=1 to 59 do write ( v1 [ i ] ) ;

writeln (' );

end

Procedure produzione2 ( n: integer; var v2 :vettore; var z :integer );

var i, q :integer ;

Begin

v2 [ 1 ] := D ;

v2[ 2 ] := G ;

if n = 1 then begin

if v2 [ n+1 ] = G then v2 [ n+2 ] :=c ;

if v2 [ n ] = D then begin

v2 [ n ] := a ;

v2 [ n+1 ] := b ;

end ;

end

else if n = 2 then begin

if v2 [ n ] = G then v2 [ n+2 ] := c ;

if v2 [ n-1 ] =D then begin

v2 [ n+1 ] := b ;

v2 [ n ] := v2 [ n-1 ] ;

v2 [ n-1 ] := a ;

end ;

for i:= 1 to 59 do begin

if v2 [ i ] =D then begin

v2 [ i+3 ] :=v2 [ i+2 ] ;

v2 [ i+2 ] :=v2 [ i+1 ] ;

v2 [ i ] :=a ;

end ;

end ;

end

else begin

q := 3 ;

for i := 1 to n do begin

if i <> n then begin

if v2 [ i ] = D then begin

if v2 [ i+1 ] = b then begin

v2 [ i+q ] := v2 [i+q-2 ] ;

v2 [ i+q-2 ] := b ;

v2 [ i+q-1 ] := v2 [ i+1 ] ;

v2 [ i+1 ] := v2 [ i ] ;

v2 [ i ] := a ;

q := q+1 ;

end

else begin

v2 [ i+q ] := v2 [ i+1 ] ;

v2 [ i+q-1 ] := b ;

v2 [ i+1 ] := v2 [ i ] ;

v2 [ i ] := a ;

q := q+1 ;

end ;

end ;

end

else begin

if v2 [ i ] = D then begin

v2 [ i+q-1 ] := v2 [ i+q-2 ] ;

v2 [ i+q-2 ] := b ;

v2 [ i+1 ] := b ;

v2 [ i ] := a ;

q := q+1 ;

end ;

end ;

end ;

for i := ( ( n*2 ) +1 ) to ( ( n*2 ) +z ) do begin

if i < > ( ( n*2 ) +z ) then begin

if v2 [ i ] =G then begin

v2 [ i+1 ]:= v2 [ i ] ;

v2 [ i ] := c ;

end ;

end

else if v2 [ i ] = G then v2 [ i ] := c ;

end ;

end ;

for i:=1 to 59 do write ( v2 [ i ] ) ;

writeln (' );

end

Function amb ( var v1,v2 : vettore ): boolean ;

var i, c: integer ;

begin

c := 0 ;

for i :=1 to 59 do if v1 [ i ] = v2 [ i ] then c := c+1 ;

if c =59 then amb := True else amb := False ;

end

begin

clrscr

v1 [ 1 ] := S ;   

v2 [ 1 ] := S ;

z := 0 ;

for i := 1 to 20 do begin

produzione1 ( i, v1, z ) ;

produzione2 ( i, v2, z ) ;

z := z+1 ;

x [ i ] := amb ( y, t ) ;

end ;

for i:=1 to 20 do begin

if x [ i ] = true then writeln ( 'La grammatica è ambigua ' )

else writeln ( ' La grammatica non è ambigua ' ) ;

end ;

readln

end

Dimostrazione pratica

Output :

abc

abc

abbcc

aabbc

aabbbccc

aaabbbcc

aaabbbbcccc

aaaabbbbccc

aaaabbbbbccccc

aaaaabbbbbcccc

aaaaabbbbbbcccccc

aaaaaabbbbbbccccc

aaaaaabbbbbbbccccccc

aaaaaaabbbbbbbcccccc

aaaaaaabbbbbbbbcccccccc

aaaaaaaabbbbbbbbccccccc

aaaaaaaabbbbbbbbbccccccccc

aaaaaaaaabbbbbbbbbcccccccc

aaaaaaaaabbbbbbbbbbcccccccccc

aaaaaaaaaabbbbbbbbbbccccccccc

aaaaaaaaaabbbbbbbbbbbccccccccccc

aaaaaaaaaaabbbbbbbbbbbcccccccccc

aaaaaaaaaaabbbbbbbbbbbbcccccccccccc

aaaaaaaaaaaabbbbbbbbbbbbccccccccccc

aaaaaaaaaaaabbbbbbbbbbbbbccccccccccccc

aaaaaaaaaaaaabbbbbbbbbbbbbcccccccccccc

aaaaaaaaaaaaabbbbbbbbbbbbbbcccccccccccccc

aaaaaaaaaaaaaabbbbbbbbbbbbbbccccccccccccc

aaaaaaaaaaaaaabbbbbbbbbbbbbbbccccccccccccccc

aaaaaaaaaaaaaaabbbbbbbbbbbbbbbcccccccccccccc

aaaaaaaaaaaaaaabbbbbbbbbbbbbbbbcccccccccccccccc

aaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbccccccccccccccc

aaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbccccccccccccccccc

aaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbcccccccccccccccc

aaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbcccccccccccccccccc

aaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbccccccccccccccccc

aaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbccccccccccccccccccc

aaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbcccccccccccccccccc

aaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbcccccccccccccccccccc

aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbccccccccccccccccccc

Questa grammatica è ambigua

Programma Grammatica aⁿbⁿcⁿ ( VI tris )

Program gram3 ;

uses crt ;

type vettore = array [ 1..60 ] of char ;

type vetbool = array [ 1..20 ] of boolean ;

var v, t, y : vettore ;

var z : vetbool ;

var i, n, q, x : integer ;

const a = char ( 'a' ) ;

const b = char ( 'b' ) ;

const c = char ( 'c' ) ;

const S = char ( 'S' ) ;

const G = char ( 'B' ) ;

procedure produzione ( n : integer; var v : vettore ) ;

var q, i, z, w, x, y, h : integer ;

var temp : char ;

begin

v [ 1 ] := S

if n = 1 then begin

v [ 1 ] = S then begin

v [ 1 ] := a ;

v [ 2 ] := b ;

v [ 3 ] := c ;

end ;

end

else begin

q := 3 ;

for i := 1 to n do begin

if i < > n then begin

if v [ i ] = S then begin

if i = 1 then begin

v [ i + q ] := c ;

v [ i+ (q-1) ] := G ;

v [ i+1 ] := a ;

q := q+2 ;

end

else begin

for z := 1 to (q-3) do v [ i+q-(z-1) ] :=v[ i+(q-3)-(z-1) ] ;

v [ i+3 ] := c ;

v [ i+2 ] := G ;

v [ i+1 ] := v [ i ] ;

v [ i ] := a ;

q := q+2 ;

end ;

end

end

else begin

for z := 1 to ( q-3 ) do v [ i + ( q-z ) ] := v [ i + ( q-3 )-( z-1 ) ]

v [ i+2 ] := c ;

v [ i+1 ] := b ;

v [ i ] := a ;

for h := 1 to n-1 do begin

for y := 1 to 60 do begin

if ( (v [ y ] = c) and ( v [ y +1 ] = G ) ) then begin

temp :=v[ y ] ;

v[y]:=v[y+1] ;

v[y+1]:=temp

end ;

end ;

end ;

for w := 1 to 60 do if ( ( v [ w-1] = b ) and ( v [ w ] = G ) ) then v [ w ] := b ;

end ;

end ;

end

Function amb ( var v1,v2 : vettore ): boolean ;

var i, c: integer ;

begin

c :=0 ;

for i :=1 to 59 do if v1 [ i ] =v2 [ i ] then c := c+1 ;

if c =59 then amb := True else amb := False ;

end

begin

clrscr

v [ 1 ] := S ;

for i := 1 to 20 do begin

produzione ( i, v ) ;

for x := 1 to 60 do begin

t [ x ] := v [ x ] ;

write ( t [ x ] ) ;

end ;

produzione ( i+1, v ) ;

for x := 1 to 60 do begin

y [ x ] := v [ x ] ;

write ( y [ x ] ) ;

end ;

z [ i ] := amb ( t, y ) ;

i := i+1 ;

end ;

for i := 1 to 20 do begin

if z [ i ] = true then writeln ( ' La grammatica è ambigua ' )

else writeln ( ' La grammatica non è ambigua ' ) ;

end ;

readln

end

Dimostrazione pratica

abc

aabbcc

aaabbbccc

aaaabbbbcccc

aaaaabbbbbccccc

aaaaaabbbbbbcccccc

aaaaaaabbbbbbbccccccc

aaaaaaaabbbbbbbbcccccccc

aaaaaaaaabbbbbbbbbccccccccc

aaaaaaaaaabbbbbbbbbbcccccccccc

aaaaaaaaaaabbbbbbbbbbbccccccccccc

aaaaaaaaaaaabbbbbbbbbbbbcccccccccccc

aaaaaaaaaaaaabbbbbbbbbbbbbccccccccccccc

aaaaaaaaaaaaaabbbbbbbbbbbbbbcccccccccccccc

aaaaaaaaaaaaaaabbbbbbbbbbbbbbbccccccccccccccc

aaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbcccccccccccccccc

aaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbccccccccccccccccc

aaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbcccccccccccccccccc

aaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbccccccccccccccccccc

aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbcccccccccccccccccccc

La grammatica non è ambigua .