CISC 223 - Assignment 1 (Winter 2024)
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CISC 223 - Assignment 1 (Winter 2024)
Due: Thursday January 25, 2:00 PM
Regulations on assignments
. The assignments are graded according to the correctness, preciseness and legibility of the solutions. All handwritten parts, including igures, 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 submission must be in one of formats: .PDF, .JPG, .PNG, .DOCX.
. Important: Assignments are evaluated based only on the iles you submit in onQ. Please be careful that you submit the correct iles and please verify your submission. Any additional material sent retroactively by email cannot be considered.
. The assignment must be based on individual work. Copying solutions from other students is a violation of academic integrity. See the course onQ site for more information.
1. (2 marks) Let Σ = fa, bg and consider languages A = fab,aa, bg, B = fba,bb, ag.
(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 Σ = f0, 1g. Let R = (01 + 001)* 0* and S = (0* 10* 1)* 0* .
(a) Give two examples of a string z that is both in R and in S (that is, z 2 R ∩ S).
(b) Give two examples of a string x that is in R and is not in S (that is, x 2 R ∩ 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 2 R ∩ S).
In each case briely explain (using natural language) why your example strings have the required property.
3. (5 marks) Show how to deine the following languages over Σ = f0, 1g 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 11011 as a preix or have 000 as a suffix.
(b) All strings that have preix 101 and have suffix 101. Note that the preix and suffx may overlap.
(c) All strings of even length that have at least one occurrence of the symbol 0.
(d) All strings that have both 01 and 10 as substrings. Note that the substrings can occur in either order and possibly overlap.
(e) All strings that do not have 000 as a substring.
4. (3 marks) Let Σ = {0, 1} 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 deines the state transitions of the diagram.
(c) What is the language recognized by the state diagram? Describe (in English) con- ditions that exactly characterize all strings in the language.
5. (2 marks) Let Σ = {a,b,c, d} and consider the nondeterministic state diagram with ε- 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 ε-transitions.
You should not further modify/simplify the resulting state diagram.
Figure 2: State diagram with "-transitions for Question 5.
6. (5 marks) Let Σ = {a; b}. 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.
2024-01-23