CS402 Assignment 3 Solution 2021 | CS402 Assignment No 3 Solution 2021 | 100% Correct Solution
CS402 Assignment 3 Solution 2021 | CS402 Assignment No 3 Solution 2021 | 100% Correct Solution for all students.
if you required assignment solution comment us in comment box i will reply you as soon as possible and send you solution file.
#TheoryOfAutomata
#cs402assignment3solution
#learningPortal
cs402 assignment no 3 solution fall 2021 ,
cs402 assignment 3 solution fall 2021 ,
cs402 assignment 3 ,
cs402 assignment ,
cs402 ,
assignment solution ,
100% correct solution for all students ,
correct solution of cs402 assignment 3 ,
cs402 3rd assignment solution ,
cs402 assignment no 3 right solution for all students of virtual university.
Deciding whether two languages are equivalent or not, example, deciding whether an FA accept any string or
not, method 3, examples, finiteness of a language
Example
Consider two languages L1 and L2, expressed by the REs r1=a* and r2=∧+aa* respectively. To determine
whether L1 and L2 are equivalent, let the corresponding FAs be
As discussed earlier, the FA corresponding to the language (L1 ∩ L2c ) ∪ ( L1c ∩ L2 ) helps in this regard i.e. if
this FA accepts any word then L1 and L2 are not equivalent other wise L1 and L2 are equivalent.
Following are the FAs corresponding to L1c and L2c
FAs corresponding to (FA1c ∩ FA2)c and (FA2c ∩ FA1)c may be as follows
Both the FAs have no final state, so these FAs accept nothing. This implies that their union will not also accept
any string. Hence FA corresponding to the language (L1 ∩ L2c ) ∪ ( L1c ∩ L2 ) accepts nothing. Thus both the
languages are equivalent.
Determining whether the two languages are equivalent or not ?
If L1 and L2 are two regular languages, then they can be expressed by FAs. As shown earlier, L1c , L2c , L1∪ L2 ,
L1∩ L2 are regular languages and the methods have already been developed to build their corresponding FAs. It
can be observed that (L1 ∩ L2c ) ∪ ( L1c ∩ L2 ) is regular language that accepts the words which are in L1 but
not in L2 or else in L2 but not in L1 . The corresponding FA cannot accept any word which is in both L1 and L2
i.e. if L1 and L2 are equivalent, then this FA accepts not even null string. Following are the methods that
determine whether a given FA accepts any words