Reference no: EM132230288

Computability, Automata, and Formal Languages Assignment -

1. What are the formal descriptions of the following DFAs?

2. For the DFAs M₁ and M₂ shown above, what are L(M₁) and L(M₂)?

3. Define the langauge A by

A = {vw | v contains at least one 1, and w contains at least 2 symbols}.

Prove that is regular by constructing a DFA that recognizes it. That is, construct a DFA M₃ and then prove that every string in A is recognized by M₃ and that every string recognized by M₃ is in A. (Formally: show that A ⊆ L(M₃) and L(M₃) ⊆ A).

4. Recall that for a string w, w^R is the reverse of that string (see Sipser, Ch. 0, "Strings and Languages"). For a language A, define A^R to be the language composed of the reverses of each string in A, or A^R := {w^R | w ∈ A}. Show that if A is regular, A^R is regular.

5. Let B be a language, and define DELETE1(B) to be the language containing all strings that can be obtained by removing exactly one symbol from a string in B. That is,

DELETE1(B) = {xz | xyz ∈ B where x, z ∈ Σ* and y ∈ Σ}.

Show that the class of regular languages is closed under the DELETE1 operation.

6. Let A/B = {w | wx ∈ A for some x ∈ B}. Informally, think of B as a set of suffixes. A/B is the language consisting of all strings that can be constructed by removing suffixes from strings in A (where the suffixes are drawn from B). So if A = {flowing, snowed} and B = {ing, ed} then A/B = {flowing, snowed, flow, snow}

(a) Why are flowing and snowed in A/B in the example shown above?

(b) Show that if A is regular and B is any language, A/B is regular.