792 views
1. Given that $A$ is regular and $(A \cup B)$ is regular, does it follow that $B$ is necessarily regular? Justify your answer.

2. Given two finite automata $M1, M2$, outline an algorithm to decide if $L(M1) \subset L(M2)$. (note: strict subset)

edited | 792 views

1. $A$ is regular ,    $A \cup B$ is regular , then $B$ is not necessary regular
example :- $A = (a+b)^*$      $B = a^nb^n \ n \geq 0$      $A \cup B$ is $(a+b)^*$       while $B$ is not regular.

2. We have two machine $M 1$ and $M 2$
draw a DFA using $M1$ and $M2$  where start state is, say,  $p0q0$ (where $p0$ is start state in $M1$ and $q0$ is start state in $M2$)
$∂(p0q0, 0) = ∂(p0, 0) \cup ∂(q0, 0)$
if $L(M1) \subseteq L (M2)$
Then final state of $M1$ will come together with final state of $M2$, while Final state of $M2$ can come alone.
i.e. all inputs of $M1$ is also in machine $M2$, and there may be different inputs in $M2$.
edited
+1
this should be done on the minimal DFA? Also how to ensure strict subset?
+4
DFA need not be minimal.

To ensure strict subset, there should be atleast one final state of M2 that appears alone.
+1
M1 and M2 even need not to be DFA, they may be NFA , resulting M1 x M2 will be DFA (that may be not minimized).
a) A is regular ,    A U B is regular , then B is not necessary regular

example :- A = (a+b)*      B = Any non regular language    A U B is (a+b)*    ,   while B is not regular.

B)

Algorithm ->

Using DFA for M1 & M2 , create product DFA. Make two copies of it.

Suppose A is final state for M1 & B is final state of M2. Assume that C is some non final state for M1 & D is some non final state for M2.

To check for subset ->

Now make A as final state whenever it is associated with some non final state for M2. If A is associated with final state of M2, then make that product state non final. This way we will calculate M1-M2. This DFA should accept Empty language otherwise L(M1) is not subset of L(M2)

To check for proper subset ->

Make B as final state, whenever it is associated with some non final state of M1. If A is associated with final state of M1, then make that product state non final. This way we will calculate M2-M1. This DFA should accept non Empty language otherwise L(M1) is not proper subset of L(M2)

if both tests pass then we can say L(M1) is proper subset of L(M2).
0

Now make A as final state whenever it is associated with some non final state for M2. If A is associated with final state of M2, then make that product state non final. This way we will calculate M1-M2. This DFA should accept Empty language otherwise L(M1) is not subset of L(M2)

M1-M2 means it will accept string w which is M1 but not in M2, M1 to be a subset of M2 no such string should be there because if some string w get accepted by M1-M2 it means there are some other strings which M1 can accept but not M2 which clearly shows M1 is not a subset of M2. So M1-M2 should accept empty language(nothing) to make M1 a subset of M2.

Similar reasoning for next one also.

0

To check for proper subset ->

Make B as final state, whenever it is associated with some non final state of M1. If A is associated with final state of M1, then make that product state non final.

I think it a typo it should be "If B is......".

Intersection of M2' and M1 should have no final states AND Intersection of M2 and M1' should have at least one final state.
0
@Vishal Goel ,you mean to say that making DFA for product of
1.M2' and M1-this dfa should have no final state
2.M2 and M1' -this dfa should have atleast one final state
???

1
2
+1 vote