Assessment details
Computing Theory COSC 1107/1105 Final Exercise Answers
1. Consider the grammar derivations below.
S ⇒ aSbb ⇒ aaSbbbb ⇒ aa#bbbb
Copyright By PowCoder代写 加微信 powcoder
S ⇒ ccBd ⇒ ccccBdd ⇒ cccc#dd
S ⇒ ccBd ⇒ ccAd ⇒ cc1A1d ⇒ cc1#1d S ⇒A⇒2A2⇒2C2⇒2cCc2⇒2c#c2
(a) From the above derivations, construct rules that must exist in any context-free grammar G for which these derivations are correct.
Answer: From the first derivation, we can see the rules must include S → aSbb and S → #. From the second derivation, we can add the rules S → ccBd, B → ccBd and B → #. From the third derivation, we can add the rules B → A, A → 1A1 and A → #. From the fourth derivation, we can add the rules S → A, A → 2A2, A → C, C → cCc and C → #.
S → aSbb | ccBd | A | # B → ccBd | A | # A→1A1|2A2|C |# C → cCc | #
(b) Assuming that these are all the rules in G, give L(G) in set notation. Answer: L(G) = {aic2jwck#ckwRdjb2i | i,j,k ≥ 0,w ∈ {1,2}∗}
(c) Is the grammar G regular? Explain your answer.
Answer: G is not regular. The rule S → aSbb is not in the form where the right-hand side is either the empty string, a single character, or a single character followed by a single variable.
(d) Is there a deterministic finite state automaton for L(G)? Explain your answer.
Answer: No. L(G) is not a regular language, as we will need a stack to keep track of the
a’s and c’as well as w ∈ {1, 2}∗.
(e) Construct a context-free grammar for the language L2 below.
L2 ={w1 a2i cj al dk bi w2 |w1,w2 ∈{1,2}∗,|w1|=|w2|,i≥1,j,k,l≥0,j
Consider xy2z. As y = aj, we have xy2z = an+jbncndn and so xy2z ̸∈ L1. This is a contradiction, and so we conclude that L1 is not regular. QED
(b) Write out the proof of the same result which uses the string b2nc2n and i = 4 instead. Which steps are different? Which steps remain the same?
Answer: The proof is below. The differences are highlighted with a box like this.
Assume that L1 is regular. Then the Pumping Lemma applies, and so there is an n ≥ 1 such that for any w ∈ L1 with |w| ≥ n, there exist strings x,y and z such that w = xyz, |xy|≤n,y̸=λandxyiz∈L1 foralli≥0.
Let ,andsow∈L1 and|w|>n. So andas|xy|≤n,wemust have that for some 1 ≤ j ≤ n.
Consider . As ,wehave andso . Thisisacon- tradiction, and so we conclude that L1 is not regular. QED
(c) Give a PDA for the language L1 = {aibjcjdi|i,j ≥ 0}. your machine deterministic or non- deterministic? Briefly explain your answer.
Answer: One such PDA is below. This machine is nondeterministic, as it contains λ transitions.
w = b2nc2n
xyz = b2nc2n
xy4z = b2n+3jc2n
xy4z ̸∈ L1
(d) Is there a context-free grammar for the language L2 = {aibjcidj|i,j ≥ 1}? Explain your answer.
Answer: No. This language is not context-free, and so there is no context-free grammar for it. The reason is that we need to record both the number of a’s and then the number of b’s, but then check the number of c’s against the number of a’s, which means discarding the number of b’s. So there can be no PDA for this language, and hence no context-free grammar.
(e) The language L3 = {aibjcidj|1 ≤ i,j ≤ 2} is regular. Construct a finite state automa- ton which accepts L3 (and only L3). Your machine can be either deterministic or non- deterministic.
Answer: Note that L3 = {abcd, aabccd, abbcdd, aabbccdd}. One such automaton is below.
(f) The language L4 = {aibjcidj|1 ≤ i,j ≤ 6} is also regular. If you were to extend your previous machine to accept this language, how many transitions would you need? In other words, if there are k transitions in your machine for L3, give a formula for your estimated number of transitions required in the machine for L4.
Answer: The machine above has 15 transitions for a language with 4 strings. L4 includes all of these, so …
(g) Give a context-free grammar for L5 = {aibjcjdi | i,j ≥ 1} with at most 4 rules. The number of rules is the number of different right-hand sides in the grammar; for example, the grammar below has 6 rules.
S → aA|Aa|a A → aBaa|Baa B → abc
S → aSd | aAd A → bAc | bc
7. Snivelling Sam the Shonky Snake Oil Salesman has heard about your work on Turing machines. This is of great interest to Sam, who wishes to set up a Gallery of Important Turing Machines which are Useful and Brilliant (GITMUB). This will showcase various Turing machines, which must be of the acceptor/rejector type (i.e. Turing machines which accept a given language by terminating in an accepting state). Sam is keen to ensure that he only has the “best and brightest” Turing machines on display from those submitted to GITMUB by the general public, and so insists on the following policy on adding machines. Let the machine to be added to GITMUB be M, and the machines already in GITMUB be M1,…,Mn. If L(M) ̸= L(Mi) for all 1 ≤ i ≤ n, then M is added to GITMUB. Otherwise, (i.e. L(M) = L(Mi) for some 1 ≤ i ≤ n) then Sam makes a choice between M and Mi, and either rejects M as a member of GITMUB, or ejects Mi from GITMUB and replaces it with M (according to what he perceives as the ‘inherent artistic merit’ of each machine). This means that Sam can boast that GITMUB’s machines are all guaranteed to be unique representatives of machines accepting a particular language.
(a) Explain why, under the above policy, GITMUB can never be guaranteed to contain more than one machine.
Answer: The problem of determining whether two Turing machines accept the same language is undecidable. So while the first machine that Sam puts in his collection will trivially accept a distinct language from the other machines already in the gallery. When it comes to adding a second machine, there is no way to guarantee that the language of the second machine is different from that of the first. So if Sam insists on this guarantee, there can never be more than one machine in GITMUB.
(b) Suggest one way that Sam could relax his policy on adding machines to the gallery in order to have a larger collection of machines in GITMUB while remaining as true as possible to his original aim.
Answer: One way
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com