edited by
4,040 views
28 votes
28 votes
  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 by

4 Answers

Best answer
46 votes
46 votes
  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 by
11 votes
11 votes
Intersection of M2' and M1 should have no final states AND Intersection of M2 and M1' should have at least one final state.
7 votes
7 votes
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).
1 votes
1 votes

we can also use set theory concept to solve question B

Algorithm:

1. Find the finite automata for B-A and check if this automata accepts empty language or not. If the automata accepts empty language then we can say B ⊆ A. else terminate the algorithm and say B⊄ A.

2. Then to say if B is proper subset or not, make a finite automata for A-B and check if it accepts empty language or not. If it does not accept empty language then we will conclude B ⊂ A else we can say B=A.   

edited by

Related questions

57 votes
57 votes
1 answer
1
Keith Kr asked Sep 10, 2014
21,843 views
Let $L_1$ be the set of all languages accepted by a PDA by final state and $L_2$ the set of all languages accepted by empty stack. Which of the following is true?$L_1 = L...
36 votes
36 votes
2 answers
4