Chapter 3: Context-Free Grammar and Syntax Analysis


2.12 EQUIVALENCE OF TWO AUTOMATAS

Automatas M 1 and M 2 are said to be equivalent if they accept the same language; that is, L ( M 1 ) = L ( M 2 ). It is possible to test whether the automatas M 1 and M 2 accept the same language ”and hence, whether they are equivalent or not. One method of doing this is to minimize both M 1 and M 2 , and if the minimal state automatas obtained from M 1 and M 2 are identical, then M 1 is equivalent to M 2 .

Another method to test whether or not M 1 is equivalent to M 2 is to find out if:

For this, complement M 2 , and construct an automata that accepts both the intersection of language accepted by M 1 and the complement of M 2 . If this automata accepts an empty set, then it means that there is no string acceptable to M 1 that is not acceptable to M 2 . Similarly, construct an automata that accepts the intersection of language accepted by M 2 and the complement of M 1 . If this automata accepts an empty set, then it means that there is no string acceptable to M 2 that is not acceptable to M 1 . Hence, the language accepted by M 1 is same as the language accepted by M 2 .




Algorithms for Compiler Design
Algorithms for Compiler Design (Electrical and Computer Engineering Series)
ISBN: 1584501006
EAN: 2147483647
Year: 2005
Pages: 108
Authors: O G Kakde

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net