Sketch of Solutions to Exercises

3.3.1

(a)

S --> BaSaB --> B#B B --> bB --> e
(b)
S --> DC i /= j --> AE j /= k A --> aA --> e B --> bB --> e C --> cC --> e D --> aDb --> aA --> bB E --> bEc --> bB --> cC
(c)
S --> aS --> B --> e B --> aSbS
(d)
S --> Dx and y differ in the number of a’s that they have --> Ex and y differ in the number of b’s that they have A --> aA --> e C --> AB D --> BaDaB --> BaC#Bmore a ’s in x --> B#CaBmore a ’s in y E --> AbEbA --> AbC#Amore b’s in x --> A#CbAmore b’s in y
(e)
S --> AaCb -a discrepency A --> DAD --> bC# S --> BbCa -b discrepency B --> DBD --> aC# S --> E E --> DED --> #DClonger right side --> DC#longer left side D --> a --> b C --> DC --> e

3.3.2
(delete C --> e) (delete D --> e) (delete S --> e)
| S' --> S | S' --> S | S' --> S | S' --> S
| S --> CD | S --> CD | S --> CD | --> e
| --> a | --> D | --> C | S --> CD
| | --> a | --> D | --> C
| | | --> e | --> D
| | | --> a | --> a
| C --> e | C --> SC | C --> SC | C --> SC
| --> SC | --> S | --> S | --> C
| --> b | --> b | --> b | --> S
| | | | --> b
| D --> CC | D --> CC | D --> CC | D --> CC
| | --> C | --> C | --> C
| | --> e

3.3.3 

    call S( ) 
    if eof then accept 
    procedure S( ) 
      call A( ) 
      call B( ) 
      return 
    end 
 
    procedure A( ) 
      do 
        call B( ) 
        call A( ) 
        call B( ) 
        return 
      or 
        call a( ) 
        return 
      until true 
    end 
 
    procedure B( ) 
      do 
        call A( ) 
        call B( ) 
        call A( ) 
        return 
      or 
        call b( ) 
        return 
      until true 
    end 

3.3.4

S --> e --> SaSbSa

3.3.5

| e|| e|S O -------|- O || || | || || || || a|||| || e| S |a || || e|A || e|| || || e| --||- O ----e-|S---|| O ---Z0-|Z0-||| oO ||| | |||| a|| -||||- --|||A |a || | || ||||||| a|| b| b|| ||||||-- a e, b e,S e, e|| ||||| b|| e |A || O A |e[source]

3.3.6

A [1,a] |---------| A[4,1][5,b] A[2,b] | | | | A[6,a][5,b] e |--------| a AA[[77,,aa]][[55,b,b]] |---------------------| A A [4,a][5,b] [8,b][5,b] | | A[6,a][5,b] A[4,b][5,b] | | |-------| | b A[7,b][5,b] A[5,b][5,b] |-------------------| | A[4,b][5,b] A[8,b][5,b] e |------------| | A A A [4,b][5,b] [8,b][5,b] [6,b][5,b] | | A[6,b][5,b] A[4,b][5,b] | | |-------| | b A[7,b][5,b] A[4,b][5,b] |------------| | A[4,b][5,b] A[8,b][5,b] e | | A A [5,b][5,b] [4,b][5,b] | | e A[5,b][5,b] | | e[source]