Fall 2008 The Chinese University of Hong Kong

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

  • Point Estimates - Anderson School District Five

    Point Estimates - Anderson School District Five

    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...
  • Vocabulary Unit #7 - Washington Township Public School District

    Vocabulary Unit #7 - Washington Township Public School District

    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 - Berry College

    Chapter 6 Energy Transfer - Berry College

    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...
  • Supply Chain Security Management  European Views Supply Chain

    Supply Chain Security Management European Views Supply Chain

    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...
  • UAlbany Green Scene - University at Albany, SUNY

    UAlbany Green Scene - University at Albany, SUNY

    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 Effects of Preference on the Transfer from

    The Effects of Preference on the Transfer from

    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...
  • The Guru's - PrimaryBlogger

    The Guru's - PrimaryBlogger

    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...
  • Fun Park Surae Its not going very well,

    Fun Park Surae Its not going very 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 &...