Consider the language of all binary strings that start and end with the same

symbol.

(a) Write the production rules of a grammar for this language. Show some

derivations to test that your grammar is correct.

(b) Design a pushdown automata (PDA) to recognise this language. Give an

implementation level description of your PDA. That is, explain what the

machine will do in plain English.

(c) Draw a diagrammatic state machine model showing all the moves of your

PDA.

(d) State carefully any assumptions you have made.