Reference no: EM132683913

Question 1: A Caesar cipher is one of the simplest and earliest known tools for encrypting text, i.e., hiding it from plain sight with a reversable technique.
To encode a string, you replace each letter with a letter shifted by some fixed number of positions later in the alphabet - wrapping around if necessary. So, for example, with a shift of 22 over the regular English alphabet {a,b,c....,z} a is replaced with c,b, is replaced by d, and so on, with z being replaced by b. Decoding the string is simply a shift in the reverse direction.

Now, consider the language

L={u#v¦u,v ∈{a,b,c,d}^*,v is equal to u with a Ceasar cipher shift of 2}
So adab#cbcd#L but adab#adab/∈L
Write a description of a Turing machine algorithm that decides L

Question 2:
Consider the language
L={u#v¦u,v ∈{a}^*,|u|and |v|have the same parity }. Parity means odd or even, so the language only includes strings where both parts are odd or both parts are even.

Draw a diagram version of a Turing machine that decides the language L.

Question 3:
Note: you must have correct solutions for Questions 5 and 6 before attempting this question.

Give the big O notation complexity for the Turing machine you described in Question 5.
Give the big O notation complexity for the Turing machine you drew for Question 6.

Question 4:
Prove that the class P of languages with known polynomial time algorithms is closed under the operations of union and concatenation.

Question 5:
Consider the language L={a^i b^j c^k |i,j,k=0,and if i=1 then j=k}
1.Show that L is not regular. Hint: the regular languages are closed under the intersection operation.

2.Show that L meets the requirements of the regular language pumping lemma. In other words, find a pumping length n and show that the conditions hold for strings longer than n

Explain why the previous two parts do not contradict each other.

Question 6. Construct context-free grammars that generate the following languages (give your answers as a set of rules):
{a^k w|w?{a,b}^*,|w|=k,k=0}
{a^k b^(n+k) a^k?{a,b}^* |n=0,k=0}