Automata Theory 1 What can be deduced about the relationship

Automata Theory 1. What can be deduced about the relationship between sets A and B if the following is true? a) A B = A b) A B = A c) A – B = A d) A B = A B e) A – B = B – A 2. Consider the following languages over {0, 1}: L1 = {w : w contains exactly two 1’s and |w| 4} L2 = {w : w doesn’t contain the same number of 0’s as 1’s and |w| = 4} Give the first 8 strings in the L-ordering of the following: a) L1 b) L2 c) L1 L2 d) L1 L2 e) L1 – L2 f) L2 – L1 3. Consider the following languages over {0, 1}: L3 = {w : does not begin and end with same symbol and |w| 3} L4 = {w : w = wR, |w| 3} Give the first 8 strings in the L-ordering of the following: a) L3 b) L4? c) L4L3 d) L33 e) L4* 4. What are the unique substrings of w = babbca over = {a, b, c}?

Solution

1. What can be deduced about the relationship between sets A and B if the following is true? a) A B = A b) A B = A c) A – B = A d) A B = A B e) A – B = B – A

a) A B = A => This implies A contain all element of B

b) A B = A => This implies B contain all element of A.

So Aand B are same

c) A – B = A => B doesn\'t have any element of A

d) A B = A B => true from a) and b)

e) A – B = B – A => B - A = A

This all conditions can only be satisfied by an empty set only as A and B are same with any common element.