CISC/CMPE 223 - Assignment 2 (Winter 2023)
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CISC/CMPE 223 - Assignment 2 (Winter 2023)
1. (4 marks) Using the method described in Section 9.1 and in class convert the following regular expression into a state diagram:
(01* + 10)* 1*
Note that the closure operation has highest precedence (see page 164 in the text). Thus the expression 01* denotes exactly one 0 followed by any number of 1’s.
Your answer should indicate how you arrived at the result:
● As intermediate steps write down the state diagrams that you construct for subex- pressions of the given regular expression, and for each intermediate step clearly indicate which subexpression it corresponds to.
● Please do not simplify/modify the state diagrams. Simplifications/modifications of the state diagrams are considered as errors when marking (independently of whether or not the state diagram remains equivalent).
Please note: The question is marked based on how well you follow the steps of the algorithm of section 9.1.1
2. (3 marks) Using the method described in Section 9.2 (and in class), convert the state
diagram given in Figure 1 into an equivalent regular expression. Here Σ = {a, b, c, d}. Your answer should include the intermediate step(s) used in the construction.
Figure 1: State diagram for Question 2.
3. Are the following languages A and B over the alphabet Σ = {a, b, c, d} regular or nonreg- ular?
. For a language that is regular, give a regular expression that defines it.
. For a nonregular language, using the pumping lemma prove that it is not regular.
(a) (2 marks)
A = { aj bk+2cm+1 | j ≥ 1, k ≥ 1, m ≥ 1} n
{ br cs+2dt+1 | r ≥ t ≥ 1, s ≥ 1}.
(b) (2 marks)
B = { aj+3b2k+2cm | j ≥ 1, k ≥ 1, m ≥ 1} n
{ br+3cs d2t一1 | r ≥ 1, s ≥ 1, t ≥ 1}
Hints: The languages A and B are each expressed as a union of two sets. If one (or both) of the sets is non-regular, this does not imply anything about the non-regularity of the union. When trying to show that a language C is non-regular, we have to apply the
pumping lemma to the entire language C (and not to the components of the union). On the other hand, if trying to show that C is regular, you can give regular expressions for the two component sets and then apply “+” .
4. (4 marks) Using the algorithm mark distinguishable pairs of states that was discussed in class in week 4 and that can be found in the course notes, minimize the number of states of the DFA depicted in Figure 2.
Your answer should indicate in detail how you arrived at the solution:
Figure 2: The DFA to be minimized in Question 4.
● For each stage of the algorithm, indicate which pair(s) of states are marked as dis- tinguishable at that stage and explain the reason why.
● Draw the minimized state diagram where each state is labeled by the corresponding names of states in the original DFA that were merged together.
5. (5 marks) Consider languages over terminal alphabet Σ = {a, b, c, d}.
● Give context-free grammars that generate the following five languages.
● In each case, also give a derivation of the specified terminal string using your gram- mar. The derivation beginning from the start variable should indicate each individual derivation step using the notation → .
(a) L1 = {b2ic3k+1 | k ≥ i ≥ 0} Derivation for the string: b2 c4 .
(b) L2 = { ai bk c2i | i ≥ 1, k ≥ 1} u {c3kdk | k ≥ 1 } Derivation for the string:
a2 bc4 .
(c) L3 = {a2ib2i+1c5k+2 | i ≥ 1, k ≥ 1} Derivation for the string: a4 b5 c7 .
(d) L4 = {a2rb3i+1c3s+1di+1 | i ≥ 1, r ≥ 1, s ≥ 1} Derivation for the string: a4 b4 c7 d2
(e) L5 = {a3i+1bi+3c2kd2k | i ≥ 0, k ≥ 0} u {a2rbs c5sdr+1 | r ≥ 0, s ≥ 0}
Derivation for the string: a2 bc5 d2 .
2023-02-27