# Fall 2008 The Chinese University of Hong Kong

Fall 2008 The Chinese University of Hong Kong CSC 3130: Automata theory and formal languages More on DFA minimization and DFA equivalence Andrej Bogdanov http://www.cse.cuhk.edu.hk/~andrejb/ csc3130 Example Construct a DFA over alphabet {0, 1} that accepts those strings that end in 111 0 0 q 1 q 1

0 q 1 q 1 q q q 1 1 q 1

0 q q 0 q 1 This is big, isnt there a smaller DFA for this? Smaller DFA Yes, we can do it with 4 states: 0 q 1 0

1 q 0 0 q 1 q 1 No smaller DFA! Last time we saw that There is no DFA with 3 states for L In fact, it is also true that This is the unique 4-state DFA for L 0 q 1

0 1 q 0 0 q 1 q 1 Theorem The DFA M found by the minimization algorithm is the unique minimal DFA for L Proof outline Suppose there are two minimal DFAs M, M for L q0 M

q0 M In both M and M, every pair of states is distinguishable Proof outline for uniqueness If M and M are not the same, there must be states q1, q2 of M and q of M like this: u q1 M q0 M q 0 v q2

For some strings u and v q u, v Proof outline for uniqueness Since q1 and q2 are distinguishable, there is a string w such that u v q1 q2 w w M M q u, v

But in M this cannot happen! w ? Testing equivalence of DFAs Two DFAs are called equivalent if they accept the same language 0 0 0 q 1 q 0 1 q 1

q 1 q 1 0 0 0 q 1 0 q q 1 0 q 0 1

qC 1 1 Testing equivalence of DFAs How can we tell if M and M are equivalent? Algorithm for testing DFA equivalence: Run DFA minimization algorithm on M Run DFA minimization algorithm on M Check that M and M are the same Example Do the following two NFAs q 0,1 1 0,1 0

q 0 q 1 1 accept the same language? q 0 Answer We cannot run minimization procedure on NFAs But we can convert both NFAs to DFA and test equivalence regular expression NFA DFA

## Recently Viewed Presentations

• Find a point estimate for the number of calories in a serving of chocolate ice cream. Calories per ½ cup serving for 16 popular chocolate ice cream is shown below. Find a point estimate for the proportion that are greater...
• adj.—open to attack; capable of being wounded or damaged, unprotected. Synonym: defenseless, unguarded. Those brave enough to have opposed the dictator's rise now found themselves in a . vulnerable. position. vulnerable
• Chapter 6 Energy Transfer CHM 108 Suroviec Spring 2014 Figure 06-T04 Title: TABLE 6.4 Caption: Specific Heat Capacities of Some Common Substances * * * * * * I. Principles of Heat Flow Energy is the capacity to do work...
• March 1-3, 2006 More information: email [email protected] ; tel. +41-76-5890967 COPYRIGHT 2003-2007. Cross-border Research Association Supply Chain Security Initiatives 1. Global voluntary ISO 28000/1/3/4 WCO SAFE TAPA… 2. Global mandatory ICAO IMO/ISPS ´Dangerous goods´… 3. North America voluntary C-TPAT CSI...
• These include: Fall energy campaign Empire Commons bill program Destination Green (Sustainable Transportation Day) Campus sustainability Day International Day of Climate Action (350.org) National Teach In on Climate change Recyclemania Earth Day Clean up day Give and Go ( formerly...
• The range for the HP toy was from 1.6 to 1.9 times per minute. In a reversal to label training, Nick correctly responded on100% of trials for both toys across two days. During the LP request test, Nick asked for...
• became the first Sikh martyr when executed on the orders of the Mughal Emperor. Guru Hargobind (1595-1644) Guru Hargobind is important to Sikhs because he: designed the Nishan Sahib (Sikh flag). wore two swords showing meeri-peeri (worldly power as well...
• click in het menu op public kahoots. zoek: game Surae. Dan: Play - Launch - Start. en speel op de telefoon . You are the manager of . F. un . P. ark Surae. The Balance sheet and Profit &...