CISC/CMPE 223 - Assignment 1 (Winter 2023)
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CISC/CMPE 223 - Assignment 1 (Winter 2023)
1. (2 marks) Let Σ = n0, 1} and consider languages A = n01, 00, 1}, B = n10, 11, 0}.
(a) Write down all strings in the set A . B . How many strings there are in A . B? (b) Write down all strings in the set B . A. How many string there are in B . A?
2. (3 marks) In this question the alphabet is Σ = na, b}. Let R = (ba + bab)* a* and S = a* b(a* ba* b)* a* .
(a) Give two examples of a string z that is both in R and in S (that is, z ● R e S).
(b) Give two examples of a string x that is in R and is not in S (that is, x ● R e S where S is the complement of S).
(c) Give two examples of a string y that is in S and is not in R (that is, y ● R e S).
In each case briefly explain (using natural language) why your example strings have the required property.
3. (5 marks) Show how to define the following languages over Σ = n0, 1} using only ε, the alphabet symbols 0 and 1, and the operations of union, concatenation, and closure.
Note: Your answer cannot use the intersection or complementation operation. Below “or” always means “inclusive or” .
(a) All strings that have both 000 and 111 as a substring.
(b) All strings that have 0000 or 1111 as a substring.
(c) All strings that do not have 111 as a substring.
(d) All strings of odd length that have 0000 as a substring.
(e) All strings w satisfying condition (i) or condition (ii):
(i) w has at most three occurrences of 0; (ii) w has at most three occurrences of 1.
4. (2 marks) Let Σ = na, b} and consider the state-transition diagram given in Figure 1.
Figure 1: State-transition diagram for Question 4.
(a) Give examples of three strings that are accepted by the state diagram and examples of three strings that are not accepted by the state diagram.
(b) Write out explicitly the transition table (or transition function) that defines the state transitions of the diagram.
5. (3 marks) Let Σ = na, b, c, d} and consider the nondeterministic state diagram with e- transitions given in Figure 2.
Using the systematic method described in the lectures (and in the text), convert the state diagram into an equivalent (non)deterministic state diagram without e-transitions .
You should not further modify/simplify the resulting state diagram.
Figure 2: State diagram with e-transitions for Question 5.
6. (5 marks) Let Σ = na, b, c}. Using the systematic method described in the lectures (the subset construction), convert the nondeterministic state diagram given in Figure 3 into a deterministic state diagram. Your answer should indicate how the deterministic state diagram is obtained from the nondeterministic one: the states of the deterministic diagram should be labeled by sets of states of the nondeterministic diagram.
Figure 3: State-transition diagram for Question 6.
2023-02-27