Solved–Problem Set 2– Solution

Description

Problem 1. (10 points)

1. Express the following language defined over the alphabet { , } as the intersection of two simpler languages: { : ℎ ^′ ℎ }

2. Construct FSAs for each of the two languages you found in part (a).

3. Use the cross-product method and combine the two FSAs in part (b) to construct an FSA for the original language.

4. Construct an FSA for the same language with fewer states by merging two of the states in your FSA in part (c). Explain why you can merge these two states without changing the language of the FSA.

Problem 2. (10 points) For any string = _{1 2} · · · , the reverse of , written , is the string in reverse order, · · · _{2 1} . For any language , let = { | ∈ }. Show that if is regular, so is .

Problem 3. (10 points)

1. Construct an FSA with 6 states to recognize ₄ = {1111}. Can you reduce the number of states below 6? (Hint: recall a basic property of directed graphs from CS 135!)

2. Use your argument to prove that, for all ≥ 3 there is a language that can be accepted by a -state FSA that cannot be recognized by any FSA with fewer states.

Optional Problem. (10 points) For any string , over alphabet Σ, we define the string ( ) as follows: if = , ∈ Σ, ∈ Σ^∗ then ( ) = . For example, (0111) = 1110, (10110) = 01101.

Prove that if is regular, then so is ( ) = { ( ): ∈ }.