COMP2270-Assignment 1 Solved

1.      If  {𝑎𝑛} and {𝑏𝑛} are two sequences, we write {𝑎𝑛} = {𝑏𝑛} if and only if 𝑎𝑛 = 𝑏𝑛, 𝑛 ∈

ℕ0 . Use mathematical induction to show that {𝑎𝑛} = {𝑏𝑛} where  

𝑎0 = 2, 𝑎𝑛 = 𝑎𝑛−1 + 3; 𝑏𝑛 = 3𝑛 + 2  

 

2.      Are the following sets closed under the following operations? Justify your answer. If not, what are their respective closures?

a.     The odd length strings over the alphabet {,, ,} under concatenation.

b.     L = {w  {,}*: w ends in } under Kleene star.

 

3.      Let

𝑺𝒂𝒎𝒆𝑪𝒐𝒍𝒐𝒖𝒓 = { (𝑎𝑝𝑟𝑖𝑐𝑜𝑡, 𝑜𝑟𝑎𝑛𝑔𝑒), (𝑎𝑣𝑜𝑐𝑎𝑑𝑜, 𝑙𝑖𝑚𝑒), (𝑙𝑖𝑚𝑒, 𝑐𝑢𝑐𝑢𝑚𝑏𝑒𝑟),

(𝑠𝑡𝑟𝑎𝑤𝑏𝑒𝑟𝑟𝑦, 𝑡𝑜𝑚𝑎𝑡𝑜), (𝑐𝑎𝑟𝑟𝑜𝑡, 𝑜𝑟𝑎𝑛𝑔𝑒) } 

be a relation defined over the set of fruits and vegetables  

𝐹𝑉 = {carrot, avocado, lime, tomato, pear, apricot, strawberry, orange, cucumber}

[Assume the colour of the given fruits are green, orange/yellow or red]

a.     Which properties of an equivalence relation does SameColour lack?

b.     What is its equivalence closure?  

c.      Represent the closure in graphical form.  

d.     How many equivalence classes are there in the closure?

4.      For each of the following statements, state whether it is True or False.  Prove your answer.

a.     L1, L2 where L1  L2 ((L1 L2)  (L2 L1)). 

b.     L1, L2 (L1 = L2 iff L1+ = L2+).   

c.      If 𝐿1 − 𝐿2 is finite, then at least one of 𝐿1 or 𝐿2 must also be finite. 

 

5.      Construct a deterministic finite state machine for each of the following languages. Give both the state-transition diagram and the quintuple representation for each.

a.     {w  {0, 1}* : w has 101 as a substring}. 

b.     {w  {a, b}* : w has neither bab nor abb as a substring}. 

             

6.      Consider the following deterministic finite state machine M 

 

  

 

Does it contain the minimum number of required states for the target language? Prove your answer using minDFSM (Rich, 2008; page 92) or, as an extra challenge, by finding the number of equivalence classes in L(M). 

 

7.      Give nondeterministic finite automata that accept each of the following languages. Provide both state-transition diagrams and the corresponding quintuple representations (M = (K, , , s, F)).

a.      The set of strings in (ab)* such that there are two a’s separated by a string whose length is 4i, for some i0. 

b.     L={ w {a,b}*; w= (ba  (( a  bb ) a b*)) }  

 

 

8.      Let M be the NDFSM below. Construct a DFSM that accepts ¬𝐿(𝑀). Show your work using the algorithm ndfmtodfsm (Rich 2008, page 75). 

  

 

9.      Convert the following FSMs to regular expressions. For part a) you MUST use the full algorithm fsmtoregex shown in class (Rich, 2008; page 142-143) and show your work including null transitions. For part b) you may use the heuristic. In both cases consider carefully which state to remove first; picking a certain state may drastically simplify the rest of the solution.

a.  

  

 

 b.  

 

  

 

10.   Consider a Dice Rolling game played between two players P and Q. Each player rolls a dice and the player with highest face value wins the roll. The player wins 3 rolls wins the game. 

a.     Define an alphabet  and describe a technique for encoding the Dice Rolling game as strings over . 

 

b.     Let LDR be the language of Dice Rolling game, encoded as strings as described in part (a), that corresponds to wins for player P.  Show a FSM that accepts LDR. [Note: you only need to consider how player P can win] 

 

11. Consider a game Magic-Cheese-Hunt. The game characters are a mouse and a number of cats living in a house. The mouse lives in a mouse hole where the game starts from; it is hungry and wanders around the house searching for cheese. There are two types of cheeses: ordinary cheese and magic cheese. Ordinary cheese only satisfies his hunger and magic cheese satisfies his hunger and makes him invisible, however, he can eat only one kind of cheese at a time. If he finds some chees he eats it and get back to one of the mouse holes

in the house. The cats in the house hunt for the mouse. As soon as the visible mouse sees a cat it should flee until there is no longer any cat around and then continue what it was doing. After the mouse gets back to its hole it becomes hungry again. Represent the behaviour of the mouse using a finite state machine. Your FSM should contain all necessary states and all possible state transitions required to match the above rules of playing Magic-Cheese-Hunt.  The transitions in your FSM should be based on what the mouse sees or gets: C (sees a cat), NC (does not see any cat), CH (gets some ordinary cheese), MC (gets some magic cheese).