For each n 1, let b(n) denote the binary representation of n, and let revb(n) denote...

 

Transcribed Image Text:

For each n 1, let b(n) denote the binary representation of n, and let revb(n) denote the reverse of b(n). Some examples of these strings are provided for various values of n in the following table: n in decimal b(n) revb(n) 5 6 12 101 110 1100 1101 13 43 101011 44 101100 101 011 0011 1011 110101 001101 Consider the alphabet = {0,1,.), and define the language L, C as follows: L(revb(n). b(n+1)|n1) Based on the table above, the following strings are in L,: 101.110, for n = 5; 0011.1101, for n = 12; 110101 101100, for n = 43. In fact, the first few elements of L, may be listed as: L= {1.10.01. 11, 11. 100, 001. 101,--- Task 3.1. Show that L, is a context-free language by constructing a pushdown automaton (PDA) that accepts L. In particular, you are required to: (a) Provide a clear description of the main idea of the design of the PDA and what the stack is used for. This should not take more than half a page. (b) Draw a transition diagram for the constructed PDA. (20) (10) For each n 1, let b(n) denote the binary representation of n, and let revb(n) denote the reverse of b(n). Some examples of these strings are provided for various values of n in the following table: n in decimal b(n) revb(n) 5 6 12 101 110 1100 1101 13 43 101011 44 101100 101 011 0011 1011 110101 001101 Consider the alphabet = {0,1,.), and define the language L, C as follows: L(revb(n). b(n+1)|n1) Based on the table above, the following strings are in L,: 101.110, for n = 5; 0011.1101, for n = 12; 110101 101100, for n = 43. In fact, the first few elements of L, may be listed as: L= {1.10.01. 11, 11. 100, 001. 101,--- Task 3.1. Show that L, is a context-free language by constructing a pushdown automaton (PDA) that accepts L. In particular, you are required to: (a) Provide a clear description of the main idea of the design of the PDA and what the stack is used for. This should not take more than half a page. (b) Draw a transition diagram for the constructed PDA. (20) (10)