Problem 1 (15 pts)
For each of the following languages give a regular expression that describes it.
A1 = {w ∈ {1,0}* | every odd position in w is a 1}.
A2 = {w ∈ {1,0}* |w contains an even number of 0s and each 0 is followed by at least one 111}.
A3 = {w ∈{0, 1, . . . , 9, .}∗ | w is a valid decimal number, i .e. no leading zeros are
Problem 2 (10 pts)
Let R = (0 ∪ 10)∗ ∪ (ε ∪ 1)1∗. construct an NFA that recognizes R. Apply the construction literally (do not optimize the resulting NFA – keep all those ε moves in the NFA).
Problem 3(20 pts)
The language A= {w ∈Σ∗|w has an even number of 1’s} is a regular language over the alphabet
Σ = {0, 1}. Answer the following question:
Formally define a DFA with 2 states that recognizes A.
Draw the state diagram for the DFA.
Convert the DFA to GNFA.
Give the regular expression that describes the language A by performing the GNFA reductions procedures discussed in class. IMPORTANT: Show all steps.
Problem 4 (20 pts)
Let L = {aibkal| l > i + k}:
List all strings in L of length 7.
Use the Pumping Lemma for Regular Languages to prove that L is not regular.
Problem 5(20 pts)
Construct a state diagram PDA for L={ w#v | wR is a substring of v and w,v ϵ{0,1}^* }
Problem 6(15 pts)
Design a context-free grammar for the language defined below. Write the set of productions and clearly mark the start symbol. Recall that |x| is the length of the string x:
L = {xyz | x, z ∈ { 0, 1}∗ , y ∈ { 2, 3} ∗ , and |x| = |y|}