Q1.7 3 Points Provide a context-free grammar in Chomsky normal form that generates the language accepted by the machine in question 1.4. You may provide a context-free grammar for partial marks if you can't provide a context-free grammar in CNGE You should provide a short explanation of why your grammar is correct, there is no need to formally prove that it generates the language. Enter your answer here You may alternatively upload a pdf containing your solution. Please select file(s) Select file(s) Q3 Every regular language is context-free 3 Points Corollary 2.32, from the Introduction to the theory of Computation - Sipser, states that every regular language is context-free. For each regular language L provide an explicit construction of a pushdown automata that recognises L. Enter your answer here You may alternatively upload a pdf containing your solution. Q4 Context-free closure properties 3 Points Let A be regular language and let B be a context-free language. Prove that A B is context-free. Enter your answer here You may alternatively upload a pdf containing your solution. Q2 Construction of a pushdown autoamata 3 Points Demonstrate that there exists a pushdown automata that recognises the following language. {w = {0,1}* ||w| = 2k +1 A wk+1 =0 for some k Z>0} You should provide a short explanation of why your pushdown machine is correct, there is no need to formally prove that it recognises the language. Enter your answer here You may alternatively upload a pdf containing your solution. Please select file(s) Select file(s) Q5 Contractable strings 7 Points A string is contractable if there is a sequence of contractions which result in the empty string, where a contraction is the removal of a sequence of length 2 or more consecutive identical symbols. When a contraction is applied it must contract a maximal length sequence of consecutive identical symbols. For example, abaaababb is contractable as witnessed by the following sequence of contractions. abaaababb abbabb abba + aa Let L be the language of contractable strings over the alphabet {a,b}. Prove that L is a context-free language and that L is not a regular language. Enter your answer here You may alternatively upload a pdf containing your solution. Please select file(s) Select file(s) Q1.7 3 Points Provide a context-free grammar in Chomsky normal form that generates the language accepted by the machine in question 1.4. You may provide a context-free grammar for partial marks if you can't provide a context-free grammar in CNGE You should provide a short explanation of why your grammar is correct, there is no need to formally prove that it generates the language. Enter your answer here You may alternatively upload a pdf containing your solution. Please select file(s) Select file(s) Q3 Every regular language is context-free 3 Points Corollary 2.32, from the Introduction to the theory of Computation - Sipser, states that every regular language is context-free. For each regular language L provide an explicit construction of a pushdown automata that recognises L. Enter your answer here You may alternatively upload a pdf containing your solution. Q4 Context-free closure properties 3 Points Let A be regular language and let B be a context-free language. Prove that A B is context-free. Enter your answer here You may alternatively upload a pdf containing your solution. Q2 Construction of a pushdown autoamata 3 Points Demonstrate that there exists a pushdown automata that recognises the following language. {w = {0,1}* ||w| = 2k +1 A wk+1 =0 for some k Z>0} You should provide a short explanation of why your pushdown machine is correct, there is no need to formally prove that it recognises the language. Enter your answer here You may alternatively upload a pdf containing your solution. Please select file(s) Select file(s) Q5 Contractable strings 7 Points A string is contractable if there is a sequence of contractions which result in the empty string, where a contraction is the removal of a sequence of length 2 or more consecutive identical symbols. When a contraction is applied it must contract a maximal length sequence of consecutive identical symbols. For example, abaaababb is contractable as witnessed by the following sequence of contractions. abaaababb abbabb abba + aa Let L be the language of contractable strings over the alphabet {a,b}. Prove that L is a context-free language and that L is not a regular language. Enter your answer here You may alternatively upload a pdf containing your solution. Please select file(s) Select file(s)
