### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Algebraic Automata Theory MAD 6616

USF

GPA 3.92

### View Full Document

## 62

## 0

## Popular in Course

## Popular in Mathematics Discrete

This 4 page Study Guide was uploaded by Elizabeth Haley on Wednesday September 23, 2015. The Study Guide belongs to MAD 6616 at University of South Florida taught by Natasa Jonoska in Fall. Since its upload, it has received 62 views. For similar materials see /class/212665/mad-6616-university-of-south-florida in Mathematics Discrete at University of South Florida.

## Reviews for Algebraic Automata Theory

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/23/15

Jan 25 2005 MAD 6616 ALGEBRAIC AUTOMATA THEORY NOTES 3 THE MYHILLNERODE THEOREM INSTRUCTOR NATASA JONOS KA 1 REDUCTION OF DFA Let M Q I T 8 be a nite state automaton De nition 11 context of a state Let q E Q The right context of the state q in M is the set RqM LMq where Mq Q qT 8 We will write only Rq when M is known Now consider the following relation on the set of states in M ql Qng if and only if Rq1 Rq2 The relation RL is an equivalence on Q and it is called the reduction on M The equivalence classes of q with respect to RL will be denoted with The automaton M is called reduced if the equivalence classes of RL are singletons ie if there are no two states with same right contexts Let M be an FSA We construct reduced automaton MRL such that MRL QRL I T 8 where q E I iff there is a q E q with q E I and q E T iff there is a q E q with q E T The edges are de ned such that qaq E 8 iff there are ql E q and qg E q with q1aq2 E 8 The name reduced automaton77 for this FSA is justi ed by the proposition below Note that in the deterministic case if qa q E 8 then for all ql E q q1aq2 E 8 implies that qg E q In other words qla q iff Vql E q qla E q Proposition 12 Let M be a FSA with no empty transitions The automaton MRL is reduced IfM is deterministic then MRL is deterministic and LMRL Proof Clearly by de nition MRL is reduced Let M be deterministic Assume that MRL is not deterministic Then there are states q q1 q2 E QRL such that q a q1 q a q2 E 8 for some a E A This means that there are states 191192 6 q and q 1 E q1 qZ E qg such that p1aq1 E E and p2aq 2 E 8 lfRq 1Rq 2 7 Q then there is a word w E Rq 1 such that w Rq 2 and in that case aw E Rp1 and aw Rp2 That is in contradiction with the assumption that L191 Hence Rq 1 Rq 2 ie all qg Now we show that LMRL Let w a1ak E Then there is a path in M p q0a1q1 qu1akqk with go 6 I and qk E T Then by de nition of MRL lqol 6 1 7 Mil 6 T and 19 lqolahlqlllqk71l7ak7lqklis a path in MRL Converse let w E LMRL and let p qu7 a17 Mil lqkql k be a path in MRL from go 6 I to qk E T with p w By the determinism of M and MRL qp ai for i 1 k implies that Vagil E qFl qpla E So there is a path from an initial state go to a terminal state qk in M with label w E Exercise 13 1 Determine whether the theorem is true if the assumption that M is deterministic is dropped7 ie whether the reduced MRL implies that LMRL L M 2 Which of the following automata are reduced the initial states are determined by an arrow pointing in and the terminal states are circled 1 2 b all states are quotso OH a a b 0 terminal a Q I 00 WC 3 FIGURE 1 2 HOMOMORPHISMS OF FSA De nition 21 homomorphism of FSA Let Mi Qi71i7Ti78i 17 2 be two FSA A homomorphism f M1 H M2 is a pair of functions 1 Q1 H Q2 and 15 81 H 82 satisfying the following three conditions V6 6 51 8 gte6 gtq86 and t gte6 gtt6 0 V6 6 81 16 2 gt56 39 qlt11 2 and gtqT1 T2 A homomorphism f gtq gte is an onto homomorphism if both 15 and 1 are so A homomorphism f q 15 is an injective homomorphism7 1 1 if 1 is so Exercise show that in that case 15 is injective too Having an equivalence relation RL it is natural to ask whether the natural map q H q is a homomorphism Proposition 22 The function f M H MRL de ned with q H q and q7a7q H qLa7 q is an onto homomomhism Proof Exercise D We will write only 1 instead of 15 or ll since most of the time it will be clear on which one of them is used In the case of deterministic FSA the conditions a and b from the de nition can be substituted with gtqa gtqa Proposition 23 If gt M a M is an automaton homomo ohlsm then LM Q LM Proof This proposition is a direct consequence of the de nition since 1 preserves paths and labels and initial state H initial state and terminal state gt gt terminal state 3 THE MYHILL NERODE THEOREM Before we state the Myhill Nerode Theorem we have to introduce some new notions De nition 31 right context of a word A right context ofa word w E 14 within language L is de ned to be the language Rw7 L um E L 1014 O L We will write just Rw when L is understood We can de ne an equivalence relation on 14 relative to L in the following way zRLy if and only if Rz7 L RyL Clearly this is an equivalence on 14 We will denote with the equivalence class of z in 14 The number of distinct equivalence classes of RL is the index of RL We can now state the Myhill Nerode Theorem and its consequences Proposition 32 MyhillNerode Theorem A language L is regular if and only if RL has a nite index In that case L is a union of RL equlualence classes Proof Assume that L is a regular language and let M Q717 T7 8 be a nite reduced deterministic automaton with a unique initial state recognizing L Assume that M is complete Let w E 14 and let q qow where go is the unique initial state in M Q7 I T7 8 Then Rw L Rq M lndeed7 if z E RwL then um E L and qowm 6 T7 so gm 6 T and z E RqM Converse7 if z E RqM then gm 6 T and so qowm E T ie um E L and z E Rw7 L So there is a oneto one correspondence between the states of M and the RL classes of 147 ie if qou qow then It is easy to see that L UqOmET Converse let L be a language Q 14 which has nite number of RL classes Note that if z E L then the whole class Q L So L must be a union of RL classes We will construct a reduced deterministic automaton M with a unique initial state recognizing L The set of states Q is the set of equivalence classes7 ie Q E 14 The initial state is 1 and is a terminal state iff z E L The transitions are de ned to be a7 mam z E 147 a E 14 Exercise show that the automaton constructed above recognizes L The formula in some sense justi es the use of the same notation RL for the equivalence relation on Q and the equivalence relation on 14 The above theorem gives an intrinsic characterization of regular languages We have had two other characterizations a a regular language is a language recognized by a FSA de nition and b a regular language is a language de ned by a regular expression Both these characterizations reffer to non unique structure FSA and regular expressions are not unique for a given language The partition of 14 determined by RL on the other hand is unique for L This partition also provides the following nice corollary Corollary 33 unique minimal automaton For euery regular language L there is a unique up to an isomorphism minimal deterministic complete automaton M with one initial state such that for euery other deterministic complete FSA M with one initial state there is an onto homomorphism from M to M Proof From the Myhill Nerode Theorem it follows that every reduced complete deterministic FSA recognizing L is isomorphic to the automaton M constructed in the proof of the theorem This isomorphism is de ned via the equality Since the reduction process de nes an onto homomorphism7 the corollary follows The Myhill Nerode Theorem gives us another tool to determine whether a language is regular or not Consider again the language L anbnl n E N Q A It is easy to see that for each i 7 j ai 7 all since bi E Rai but bi Ra7 So the index of RL is in nite Exercise 34 1 Show that there is a regular language with no unique minimal non deterministic FSA 2 Show that there is a regular language with no unique minimal deterministic FSA with more than one initial state 3 For each of the regular languages in the previous examples construct the unique minimal DFA with one initial state 4 Using the Myhill Nerode Theorem determine which of the languages in exercise 14 notes 2 are regular 5 For the following languages over alphabet a7 b7 determine whether they are regular and if so7 nd their unique minimal DFA with one initial state 0 Language with even number of Us between any two a s 0 Language that has words with no two Us in a row 0 Language with words ending with aba

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.