AE2MAL: Machines and their Languages
Coursework 2: Context Free Languages
Spring 2015
Deadline: Friday, May 8th, 2015, 09:00 am
Cut-off Date: Saturday, May 9th, 2015, 09:00 am Weight: 15% of the module mark
How to submit: Via Moodle
Before even attempting to do your coursework, read this entire document carefully. Failing to observe the points mentioned in this document could cost you all the marks for the coursework.
Important instructions
Like your previous coursework, this one is also mathematical in nature and as such, your answers should be written clearly and with an appropriate degree of precision. Your task will consist in answering one question which has three parts. Regarding the presentation of your coursework, you should observe the following:
Typesetting: You should typeset your answers using a suitable software (prefer- ably LATEX, or at least LibreOffice or MS Word).
If you intend to scan a handwritten document, then you must write in clear and readable handwriting. If I cannot read any part of your answer, then I will not be able to give any marks to that part.
File type: You must generate one single pdf file of your answer and upload it to the Moodle.
Late Submissions: For every one hour delay in your submission you will lose 4% of the mark. No submissions will be accepted after the cut-off time of Saturday, May 9th, 2015, 09:00 am.
Your details on the answer sheet: Please do not forget to include your name and ID on the answer sheet.
1
Question (15)
Let b(n) denote the binary representation of n ≥ 1, with leading zeros omitted. For example, b(5) = 101 and b(12) = 1100. Consider the alphabet Σ = {0, 1, ♦}.
(a) Show that the set
is not a context free language over the alphabet Σ. (5)
L {b(n)♦b(n + 1) | n ≥ 1}
(b) Now for each n ≥ 1, let revb(n) be the reverse of b(n). For instance, revb(5) =
101 and revb(12) = 0011. Show that the set
Lr {revb(n)♦b(n+1)|n≥1}
is indeed a context free language by providing a clear and detailed description of a pushdown automaton that accepts Lr.
This includes both a verbal description of the main idea of the design of the PDA and what the stack is used for, and also a clear presentation of the tran- sition function by either a table or a transition diagram. You can see Example 5.3 on page 167 of your textbook to get an idea of how the transition function can be represented by a transition diagram or a table. (5)
(c) Design a context free grammar G for which Lr = L(G). Again remember to write down all the production rules clearly and give a verbal account of the main points of your answer such as what each variable is used for. (5)
Note: Your answers should be clear yet succinct. For instance, for part (b), you should come up with a PDA with as few states and transitions as possible. For part (c), your grammar should have as few production rules as necessary.