### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Computational Models CMPS 130

UCSC

GPA 4.0

### View Full Document

## 42

## 0

## Popular in Course

## Popular in ComputerScienence

This 7 page Class Notes was uploaded by Dr. Elyssa Ratke on Monday September 7, 2015. The Class Notes belongs to CMPS 130 at University of California - Santa Cruz taught by Staff in Fall. Since its upload, it has received 42 views. For similar materials see /class/182258/cmps-130-university-of-california-santa-cruz in ComputerScienence at University of California - Santa Cruz.

## Reviews for Computational Models

### 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/07/15

52 CHAPTER 1 FINITE AUTOMATA AND REGULAR LANGUAGES catenation and Kleene star we can build numerous languages from our building blocks To convey this process more precisely we make the follow ing de nition A regular expression over an alphabet 2 is defined as follows Q is a regular expression Each member of E is a regular expression If p and q are regular expressions then so is p U q If p and q are regular expressions then so is p o q If p is a regular expression then so is p Dana s As an example if the alphabet 2 were x y 2 then x U z 0 y would be a regular expression since 2 0 y would be a regular expression by Rule 1 and hence x U z 0 y would be a regular expression by Rule c Each regular expression r over some alphabet 2 represents a language denoted by Lr that is constructed from our building blocks More pre cisely L is the language and for each x E 2 Lx is the language x Furthermore if p and q are regular expressions then L p U q Lp U Lq L p o q Lp Lq and Lp Lp For example the expression x U z o y represents the language x zy That is it represents the language generated by forming theunion of x with the language ob tained by concatenating z and y In a similar manner the expression x 0 3quot U 2 obtained by applying Rule 1 to x and y then Rule e to x o y and z and nally Rule c to x 0 yr and 2 represents the language that consists of strings of zero or more copies of the pattern xy in addition to strings of zero or more 23 Thus regular expressions provide yet another means in addition to transition diagrams automata and grammars of specifying languages Theorem 16 shows why we are interested in languages that are represented by regular expressions C gwm 02635 THEOREM 16 Given an alphabet E the regular languages over 2 are exactly the languages that are represented by r gular expressions over 2 PROOF We glam Rf MFA e g l First we must show that the language represented by any r gular expression is regular We have already seen that the language Q is regular as well as any language containing a single string More gver we have seen that the union and concatenation of two regular languages is always regular and that the Kleene star of any regular language is regular Thus this first step of our proof is complete Next we show that any language accepted by a nite automaton can also be represented by a regular expression We assume that T REGULAR EXPRESSIONS 53 is a transition diagram for some nite automaton and show by induction on the number of states in T that are not initial or accept states that there is a regular expression that represents the lan guage accepted by T The diagrams we will consider are slightly more general than traditional transition diagrams in that their arcs can be labeled by regular expressions T o traverse such an arc requires that the machine read a pattern compatible with the expression It the languages accepted by such generalized diagrams can be rep resented by regular expressions then any language accepted by a traditional transition diagram for a finite automaton can also be so represented Qur induction process assumes that T has only one accept state Otherwise for each accept statemwdf T in which only that state was an accept state nd regular expres sions associated with each of these diagrams and then form the union of these expressions to obtain the desired expression for T To begin our Masties BEQSS tlE 1 JStB i m h ti seasralizisiiaarisi adiagemmtemrmh 0111 onigg srztstatsratdthat i anixitialstste 9r sesscept state There are two possrbilities Either T contains only one statei tliat isiboth the initial state and the accept state or T contains two states of which one is the initial state and the other is the accept state In the former case the desired expression is merely the Kleene star of the union of the labels that appear on the arcs in the diagram The latter case is a bit more complex If there are multiple arcs connecting the same states in the same direction we replace them with a single arc labeled by the regular expression that represents the union of the original labels At this point T can contain at most four arcs one from the initial state back to the initial state one from the initial state to the accept state one from the accept state back to the accept state and one from the accept state to the state Let us denote these arcs with the labels r s t and u respectively see Figure 130 u Figure 130 The possible arcs in a transition diagram with two states one an initial state and the other an accept state 64 CHAPTER 1 FINITE AUTOMATA AND REGULAR LANGUAGES If the arc labeled 3 is not present in the diagram then the asso ciated regular expression is Q since there would be no way to reach the accept state from the initial state Otherwise the structure of the associated regular expression depends on the absence or pres ence of the arc labeled u If this arc is not present then the expression Tl 5 ta is the desired regular expression where r and t are replaced by Q if the corresponding arc is not present in the diagram If there is in fact an arc from the accept state to the state then the expression T S t u lrl s t Sf kg is the desired expression where again r 55 replaced by E if the corresponding arc is not present in T Let us now suppose that n E N and that the language accepted by any generalized nansition diagram with no more than 11 states that are not or accept states can be represented by a regular expression For any generalized transition diagram having 11 1 states that are not initial or accept states we proceed as follows refer to Figure 131 Select a state so in T that is not an accept state or an initial state Remove this state and all its incident arcs from T For each pair of removed arcs one leading to so from another state and the other leading away from so to another state labeled p and q respectively draw an arc from the origin of the arc la w Mil hli Fam p r oq O 5 Figure 131 Removing a state so from a generalized transition diagram for a fir automaton Note Whenever binary set operators are used on regular expressions they will be de ned for the purposes of these problems acting on the corresponding regular languages eg for regular expressions t and u t g u whenever the regular language corresponding to t is a subset of the regular language corresponding to 259 De ne the function SET such that 1 N K and 2 arr for any a E 2and any a E 2 Prove the following facts about rev 2 gt 2 yTrT for any strings 3 y E 2 Proof We proceed by induction on the length of y The base case 0 atA quot CUT Araquot yrx quot Hence it suffices to show that for any 71 2 0 if yrx quot for any strings 3y E 2 such that n then wz quot Tw quot for any strings w z E 2 such that z 71 1 Let z E 2such that gzg 71 1 Without loss of generality we may assume that z ay where a E 2 y E 2 and 72 Then sz yrwar yrawr ayYW zrwr E b 377 a for any string a E 2 Proof By induction on the length of The base case 0 is covered by 1 in the de nition of rc39v Hence it suffices to show that for any 71 2 0 if CCTV a for any string a E 2 such that n then 27 z for any string 2 E 2 such that gzg 72 1 Without loss of generality we may assume that z or where a E 2 a E 2 and 72 Then using the results from part ZTY stray aatrr or z E c for any string a E 2 and any 71 2 0 Proof By induction on 71 The base case 71 0 30T A A 00 Hence it suffices to show that for any string a E 2 assuming that 37quot 1Y gown 1 Then using the result from part Mn1V rn lrar xrn 1xr D 34 Show that 111 11111 Proof Assume that 2 Since A E 111 7 11 111 it suffices to show that 1quot E 11111 and 1quot E 111 whenever 71 2 2 1quot E 111 whenever 71 2 2 1quot E 111 g 111 whenever 71 2 2 1quot E 11111 whenever 71 2 2 If 71 is even then 1quot E 11 g 11111 If 71 2 2 is odd then 71 3 2 0 is even and 13 111 E 11111 hence 1quot 213 E 11111 But Kleene star is closed under concatenation ie t 2 whenever t 2 u and t Qv so that 1quot 1 1313 e 11111 1 37 Describe the smallest set of languages that contain the basic languages A and for every 1 E 2 and is closed under the following operations union The set of all nite languages consisting of elements of 2 ie strings consisting of a single element 2 b concatenation The set of all languages containing a single nite length string com posed of elements of 2 d union and concatenation The set of all nite languages 320

### 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."

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### 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.