^^Parentesi delle espressioni, con le operazioni binarie.

() una coppia di parentesi vuota, o una lettera
rappresenta una espressione elementare (o simbolo terminale, o termine finale)

es: l'espressione piu' semplice

  simbolo
terminale		 coppia di
parentesi vuota
senza ()
esterna		 
 a(aa)
 
 ()(()())
con ()
esterna		 
(a(aa))
 
(()(()()))

Notazione

per regolarita' l'espressione avra' sempre la coppia di parentesi esterna.

"solo da 1 parte"

l'espressione viene composta, componendo sempre

(()(()()))   e' il caso piu' semplice

Sostituire alla () coppia di parentesi vuota, un simbolo terminale

usiamo sempre lo stesso simbolo, ma e' da intendersi come segnaposto sostituibile da valori diversi

(()(()()))
(a (a a ))   disposto per evidenziare la corrispondenza
(a(aa))      scritto stretto

Rifatto con espressione piu' complicata

(()(()(()(()(()(()()))))))
(a (a (a (a (a (a a )))))) disposto per evidenziare la corrispondenza
(a(a(a(a(a(aa))))))        scritto stretto

Scomposizione

(()(()(()(()(()(()()))))))
 ()(()(()(()(()(()())))))
    ()(()(()(()(()()))))
       ()(()(()(()())))
          ()(()(()()))
             ()(()())
                ()()

L'espressione viene composta, componendo sempre

((((((((((((ab)b)b)b)b)b)b)b)b)b)b)b)
 

La 1 e' una parte della 2

1.                (()(()(()(()(()(()()))))))
2. (()(()(()(()(()(()(()(()(()(()(()())))))))))))
 

Da una parte o dall'altra, ma solo 1 all'estremo

(()(((()())())()))
(()(()()))
(()((()())()))
 

Parentesi qualsiasi

7 coppie di parentesi

((ab)((a((ab)b))(ab)))
 (  )(              )
      (        )(  )
       a(      )
         (  )b

 

20 coppie di parentesi

((ab)((ab)(a((((ab)b)((ab)(a((a(ab))b))))((ab)((a(ab))b))))))
 (ab)(                                                     )
  ab  (ab)(                                               )
       ab  a(                                            )
             (                          )(              )
              ((ab)b)((ab)(a((a(ab))b)))  (ab)((a(ab))b)
               (ab)b  (ab)(a((a(ab))b))        (a(ab))b
                ab     ab  a((a(ab))b)          a(ab)            
                             (a(ab))b             ab
                              a(ab)
                                ab
 
((ab)((ab)(a((((ab)b)((ab)(a((a(ab))b))))((ab)((a(ab))b))))))
 (ab)((ab)(a((((ab)b)((ab)(a((a(ab))b))))((ab)((a(ab))b)))))
  ab  (ab)(a((((ab)b)((ab)(a((a(ab))b))))((ab)((a(ab))b))))
       ab  a((((ab)b)((ab)(a((a(ab))b))))((ab)((a(ab))b)))
             (((ab)b)((ab)(a((a(ab))b))))((ab)((a(ab))b))
              ((ab)b)((ab)(a((a(ab))b)))  (ab)((a(ab))b)
               (ab)b  (ab)(a((a(ab))b))        (a(ab))b
                ab     ab  a((a(ab))b)          a(ab)            
                             (a(ab))b             ab
                              a(ab)
                                ab
 
((ab)((ab)(a((((ab)b)((ab)(a((a(ab))b))))((ab)((a(ab))b))))))
  ab   ab  a    ab b   ab  a  a ab  b      ab   a ab  b     
  ab   ab  a    ab b   ab  a  a ab  b      ab   a ab  b    
       ab  a    ab b   ab  a  a ab  b      ab   a ab  b   
                ab b   ab  a  a ab  b      ab   a ab  b  
                ab b   ab  a  a ab  b      ab   a ab  b 
                ab b   ab  a  a ab  b           a ab  b
                ab     ab  a  a ab  b           a ab             
                              a ab  b             ab
                              a ab 
                                ab
 
121 
(a(a(((a((((((ab)(((a(ab))b)(((a((((ab)b)(((ab)(a(ab)))b))(a(a(a(ab))))))b)b)))b)((a((a(ab))((ab)b)))((a((((a(ab))b)b)b))(((a(a(ab)))b)b))))b)b))b)(a((((a((((ab)b)b)b))b)(a(ab)))(a((((a(ab))b)((((a((a((a((ab)(a((a(ab))b))))b))(a((ab)(ab)))))b)(a(a((a(ab))(((ab)b)(((((a(a(a(ab))))(ab))((a((ab)((ab)(a(((((a((ab)b))(ab))b)b)b)))))b))b)b))))))(((ab)b)b)))(ab))))))))
(a(a(((a((((((ab)(((a(ab))b)(((a((((ab)b)(((ab)(a(ab)))b))(a(a(a(ab))))))b)b)))b)((a((a(ab))((ab)b)))((a((((a(ab))b)b)b))(((a(a(ab)))b)b))))b)b))b)(a((((a((((ab)b)b)b))b)(a(ab)))(a((((a(ab))b)((((a((a((a((ab)(a((a(ab))b))))b))(a((ab)(ab)))))b)(a(a((a(ab))(((ab)b)(((((a(a(a(ab))))(ab))((a((ab)((ab)(a(((((a((ab)b))(ab))b)b)b)))))b))b)b))))))(((ab)b)b)))(ab))))))))
 
121
   (
   a
+9 (a(((a(((((
0  (ab)
+1 (
0  ((a(ab))b)
+4 (((a((
0  ((ab)b)
-2 ((
0  (ab)(a(ab))
-3 )b))
0  (a(a(a(ab))))
-7 ))b)b)))b)
+3 ((a(
0  (a(ab)) ((ab)b)
-2 ))
+1 (
0  (a((((a(ab))b)b)b))
0  (((a(a(ab)))b)b)
-6 )))b)b))b)
+3 (a((
0  ((a((((ab)b)b)b))b) (a(ab))
-1 )
 
+3 (a((
0  ((a(ab))b)
+9 ((((a((a((a(
0  (ab) (a((a(ab))b))
-4 ))b))
+2 (a(
0  (ab)(ab)
-5 ))))b)
+3 (a(a(
0  (a(ab))
+1 (
0  ((ab)b)
+3 (((
0  ((a(a(a(ab)))) (ab)
-1 )
+3 ((a(
0  (ab)
+1 (
0  (ab)
+5 (a((((
0  (a((ab)b)) (ab)
-17 )b)b)b)))))b))b)b))))))
0  (((ab)b)b)
-2 ))
0  (ab)
-6 )
)))))
)

 

Links