Completely random selection of possible test questions

1. Build the GNF for the following grammar (already in CNF):

   S ->  AA |  0
   A ->  SS |  1
 

2.  Construct an FA for the following regular expression:

	10 + (0 + 11)0*1


3.  Prove that L = { 0^i 1^j | the greatest common divisor of i and j is 1} is not regular.



4.  Palindromes are words that read the same forwards and backwards.  Give a grammar for all palindromes over 0,1.



5.  Construct a PDA equivalent to the following grammar:

    S-> aAA   A -> aS | bS | a



6.  Show that L = {a^n b^n c^m | n <= m <= 2n} is not Context Free?



7.  Is L = { wRw |  R is the reverse of w}   context free?  (give a grammar or PDA if it is; prove if its not.)