PROBLEM SET 5 SOLUTIONS
UNIVERSITY OF MIAMI
BURTON ROSENBEG
(C) 2020 ALL RIGHTS RESERVED
    

{a^i b a^(2i) | i >=0 } is not regular.
 
1. A announces some number p>0. It doesn't matter exactly the number.
2. P announces the string s = a^p b a^(2p)
3. J checks that |s|>=p and s in the language
4. A can only answer with a y of the form a^j for 0<j<=p.
5. P says i = 0. 
6. J checks that a^(p-j) b a^(2p) is not in the language and concludes 
   that the language is not regular
   

{w # w^R} is not regular.

1. A announces some number p>0
2. P announces the string s = 0^p # 0^p
3. J checks that |s|>p and s is in the language.
4. A can only answer with a y of the form 0^j for  0<j<=p.
5. P says i = 0.
6  J checks that 0^(p-j) # 0^p is not in the language and concludes
   that the language is not regular
   
The set of strings (abc)* of the alphabet {a,b,c} is regular

1. A announces p is 3 or greater. 
2. P can only propose a string of the form s = (abc)^j where j>0
3. J checks that |s|>=p and s is in the language
4. A can always answer x is empty and y = abc
5. For every i, A checks that (abc)^i(abc)^(j-1) = (abc)^k for some k, 
   is in the languag. 
6. J acquits. The language cannot be shown to be non-regular

The set of strings {a^i | i is a multiple of 10} is regular

1. A announces p is 10 or greater.
2. P can only propose a string of the form s = a^(10j), j>0.
3. J checks that |s|>=p, and s is in the language
4. A can always answer x is empty and y = a^10
5. For every i, P checks that (a^10)^i a^(10j-10) is in the language
6. J acquits. The language cannot be shown to be non-regular


Exercise 2.1, 2.4 and 2.6. 

2.1 a)
            E
            |
            +-- T
                |
                +-- F
                    |
                    +-- a
                    
2.1 b)
            E
            |
            +-- T
            |   |
            |   +-- F
            |       |
            |       +-- a
            +-- + 
            |       
            +-- E
                |
                +-- T
                    |
                    +-- F
                        |
                        +-- a
         
2.1 c)

            E
            |
            +-- T
            |   |
            |   +-- F
            |       |
            |       +-- a
            +-- + 
            |       
            +-- E
                |
                +-- T
                |   |
                |   +-- F
                |       |
                |       +-- a
                +-- +
                |
                +-- E
                    |
                    +-- T
                        |
                        +-- F
                            |
                            +-- a
                            
                            
2.1 d)

       E
       |
       +-- T
           +-- F
               |
               +-- (
               |
               +-- E
               |   |
               |   +-- T
               |       |
               |       +-- F
               |           |
               |           +-- (
               |           |
               |           +-- E
               |           |   |
               |           |   +-- T
               |           |       |
               |           |       +-- F
               |           |           |
               |           |           +-- a
               |           +-- )
               +-- ) 
               

2.4 b)
     
     S -> 0 A 0 | 1 A 1
     A -> eps | 0 A | 1 A
     
2.4 c)

     S -> T | 0 0 S | 0 1 S | 1 0 S | 1 1 S
     T -> 1 | 0

2.4 e)

     S -> 0 S 0 | 1 S 1 | 0 | 1 | eps
     
2.4 f)
   
     no rules
     
2.6 b)

     S -> A b a A | B
     A -> a A | b A | eps
     B -> C | D | a B b
     C -> a | a C
     D -> b | b D
     
2.6 d)

    S -> B | A # B | B # A | A # B # A
    A -> a A | b A | # A | eps
    B -> eps | a B a | b B b | C
    C -> eps | a | b | # | # A #