Reference no: EM133309434

Problem 1: For any string w = w₁w₂......w_n, the reverse of w, written w^R, is the string w in reverse order, w_n ......w₂w₁ For any language A, let A^R = {w^R|w∈A).

Show that if A is regular, so is A^R.

Problem 2: For any language L over an alphabet Σ we say that string u ∈ Σ* is compatible with string v ∈ Σ* if for every x ∈ Σ*, ux ∈ L if and only if vx ∈ L.

a) Prove that compatibility defines an equivalence relation over Σ*. It follows that the relation partitions Σ* into disjoint subsets of strings; strings within any one partition are all pairwise compatible.

b) Show that if 1 is the regular language recognized by a DFA with n states, then the number of equivalence classes of L under the compatibility relation is no greater than n.

c) Give a high-level description of an algorithm which, given an n-state DFA for L computes the exact number of equivalence classes of L under the compatibility relation.

d) Show that L is regular if and only if the number of equivalence classes of 1 under the compatibility relation is finite. To get started, suppose there are n equivalence classes C₁, ..., C_n and let s_i;∈C_i 1 ≤ i ≤ n. Construct a DFA with state q_i, for equivalence class C_i. If, for a∈Σ s_ia and s_j; are compatible then how would you use that to define δ?

e) Use the result of part (d) to prove that the language (0ⁿ1ⁿ: n ≥ 0} is not regular, without using the pumping lemma.

Problem 3:

a) Show that the language

L = {aⁱb^jc^k: i, j, k ≥ 0 and i = 1 => j = k)

satisfies the three conditions of the pumping lemma. Hint: set the pumping threshold to 2 and argue that every string in L can be divided into three parts to satisfy the conditions of the pumping lemma.

b) Prove that L is not regular. Note that L = b*c* U aaa"b*c* u (abⁱcⁱ: i ≥ 0), and use the fact that regular languages are closed under complement and difference.

c) Explain why parts (c) and (d) do not contradict the pumping lemma.

Problem 4: Define the languages:

L_add = {aⁱb^i+jc^j:i,j≥0}

L_mult = {aⁱb^ijc^j:i,j≥0}

For each language, what is the smallest class it belongs to (regular, context-free, or TM- decidable)? Justify your answer - for example, if you claim context-free, then give a CFG/PDA for it and prove that it is not regular.