CISC/CMPE 223 - Assignment 2 (section 2) (Fall 2020)

Due: Thursday October 8, 2:00 PM (Kingston time)

Regulations on assignments

? The assignments are graded according to the correctness, preciseness and legibility of

the solutions. All handwritten parts, including figures, should be clear and legible. This

assignment is marked out of 20 possible marks.

? Please submit your solution in onQ before the due time.

? The assignment must be based on individual work. Copying solutions from other

students is a violation of academic integrity. See the course web site for more information

https://research.cs.queensu.ca/home/cisc223/2013w/#AS

1. (4 marks) Using the method described in Section 9.1 and in videos of Week 3 (video 12)

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 subexpressions

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 videos of Week 3), 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.

1An NFA produced by some other method is considered incorrect independently of whether or not it may

define the same language.

Figure 1: State diagram for Question 2.

3. Are the following languages A and B over the alphabet Σ = {a, b, c, d} regular or nonregular?

? 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 = {d

2j+1c

k+1 | j ≥ k ≥ 0} · {c

r+2b

2s+3 | r ≥ 0 and s ≥ 0}

(b) (2 marks) B = {a

2j+2b

k+3c

j+1 | j ≥ 1 and k ≥ 1} · {d

m+3 | m ≥ 0}

Above “·” stands for language concatenation.

Hints: The languages A and B are each expressed as concatenation of two components.

If one (or both) of the components is non-regular, this does not imply anything about the

non-regularity of the concatenation. If 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 individual

components of the concatenation).

On the other hand, if trying to show that C is regular, we can find regular expressions

for the two components separately and then use the concatenation operation.

4. (3 marks) Using the algorithm mark distinguishable pairs of states that was presented in

videos of Week 4 (videos 23–24) 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:

? For each stage of the algorithm, indicate which pair(s) of states are marked as distinguishable

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.

Figure 2: The DFA to be minimized in Question 1.

5. (6 marks) Consider languages over terminal alphabet Σ = {a, b, c, d}.

? Give context-free grammars that generate the following four languages.

? In each case, also give a derivation of the specified terminal string using your grammar.

The derivation beginning from the start variable should indicate each individual

derivation step using the notation ?.

(a) A = { aib2i| i ≥ 1 } ∪ {c3kdk| k ≥ 1 } Derivation for the string c

9d3

(b) B = { a3ib4kc3kd2i| i ≥ 0, k ≥ 0 } Derivation for the string a

k+1 | i ≥ 0, k ≥ 0 } Derivation for the string a

3i+1 | i ≥ 0, k ≥ 0 } ∪ { b2k+1 | i ≥ 0, k ≥ 0 }

Derivation for the string.

版权所有：编程辅导网 2018 All Rights Reserved 联系方式：QQ:99515681 电子信箱：99515681@qq.com

免责声明：本站部分内容从网络整理而来，只供参考！如有版权问题可联系本站删除。