### Create a StudySoup account

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

Already have a StudySoup account? Login here

# FoCS Week 12 CSCI 2200

RPI

### View Full Document

## 10

## 0

## Popular in Foundations of Computer Science

## Popular in ComputerScienence

This 141 page Class Notes was uploaded by thersh on Sunday May 1, 2016. The Class Notes belongs to CSCI 2200 at Rensselaer Polytechnic Institute taught by Petros Drineas in Spring 2016. Since its upload, it has received 10 views. For similar materials see Foundations of Computer Science in ComputerScienence at Rensselaer Polytechnic Institute.

## Reviews for FoCS Week 12

### 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: 05/01/16

Models of Computation Computation CPU memory temporary memory input memory CPU output memory Program memory f (x) x Example: temporary memory input memory CPU output memory Program memory compute xx 2 compute x x f (x) x3 temporary memory input memory x 2 CPU output memory Program memory compute xx 2 compute x x temporary memory f (x) x3 z 2*2 4 f (x) z*2 8 input memory x 2 CPU output memory Program memory compute xx 2 compute x x temporary memory f (x) x3 z 2*2 4 f (x) z*2 8 input memory x 2 CPU f (x) 8 Program memory output memory compute xx 2 compute x x Automaton temporary memory Automaton input memory CPU output memory Program memory Different Kinds of Automata Automata are distinguished by the temporary memory • Finite Automata: no temporary memory • Pushdown Automata: stack • Turing Machines: random access memory Finite Automaton temporary memory Finite input memory Automaton output memory Example: Vending Machines (small computing power) Pushdown Automaton Stack Push, Pop Pushdown input memory Automaton output memory Example: Compilers for Programming Languages (medium computing power) Turing Machine Random Access Memory Turing input memory Machine output memory Examples: Any Algorithm (highest computing power) Power of Automata Finite Pushdown Turing Automata Automata Machine Less power More power Solve more computational problems Languages A language is a set of strings String: A sequence of letters Examples: “cat”, “dog”, “house”, … Defined over an alphabet: a,b,c,,z Alphabets and Strings We will use small alphabe a,b Strings a u ab ab abba v bbbaaa baba w abba aaabbbaabab String Operations w a1 2a n abba v b b b 1 2 m bbbaaa Concatenation wv a1 2a bn 1 2 m abbabbbaaa w a1 2a n ababaaabbb Reverse w a a a bbbaaababa n 2 1 String Length w a a a 1 2 n Length: w n Examples: abba 4 aa 2 a 1 Length of Concatenation uv u v Example: u aab, u 3 v abaab, v 5 uv aababaab 8 uv u v 35 8 Empty String A string with no letter: Observations: 0 w w w abba abba abba Substring Substring of string: a subsequence of consecutive characters String Substring abbab ab abbab abba abbab b abbab bbab Prefix and Suffix abbab Prefixes Suffixes abbab w uv a bbab prefix ab bab suffix abb ab b abba abbab Another Operation w w n Example:abba abbaabba 0 Definitiow abba0 The * Operation * : the set of all possible strings from alphabet a,b * ,a,b,aa,ab,ba,bb,aaa,aab, Languages A language is any subs* of Example: a,b * ,a,b,aa,ab,ba,bb,aaa, Languages a,aa,aab {,abba,baba,aa,ab,aaaaaa} Note that: Sets {}{} Set size {} 0 Set size {} 1 String length 0 Another Example An infinite languaL {a b : n 0} ab L abbL aabb aaaaabbbbb Operations on Languages The usual set operations a,ab,aaaa bb,ab {a,ab,bb,aaaa} a,ab,aaaa bb,ab {ab} a,ab,aaaa bb,ab a,aaaa Complement: L *L a,ba ,b,aa,ab,bb,aaa, Reverse Definition:L {w :wL} R Examples:ab,aab,baba ba,baa,abab n n L {a b :n 0} L {b a :n 0} Concatenation Definition:L1 2 xy: xL 1 yL 2 Example:a,ab,ba b,aa ab,aaa,abb,abaa,bab,baaa Another Operation DefinitionL L n a,b3 a,b a,b a,b aaa,aab,aba,abb,baa,bab,bba,bbb Special casL a,bba,aaa More Examples n n L {a b :n 0} 2 n n m m L {a b a b :n,m 0} 2 aabbaaabbbL Star-Closure (Kleene *) 0 1 2 DefinitionL* L L L Example: , a,bb * a,bb, aa,abb,bba,bbbb, aaa,aabb,abba,abbbb, Finite Automata Finite Automaton Input String Output “Accept” Finite or Automaton “Reject” Transition Graph a,b q5 a,b b a a b q a q b q b q a q 0 1 2 3 4 initial accepting state state transition state Initial Configuration Input String a b b a a,b q 5 b a a a,b a b a q 0 q1 b q2 b q3 q4 Reading the Input a b b a a,b q 5 b a a a,b a b a q 0 q1 b q2 b q3 q4 a b b a a,b q 5 b a a a,b a b a q 0 q1 b q2 b q3 q4 a b b a a,b q 5 b a a a,b a b a q 0 q1 b q2 b q3 q4 a b b a a,b q 5 b a a a,b a b a q 0 q1 b q2 b q3 q4 Input finished a b b a a,b q 5 b a a a,b a b a q 0 q1 b q2 b q3 q4 accept Rejection a b a a,b q 5 b a a a,b a b a q 0 q1 b q2 b q3 q4 a b a a,b q 5 b a a a,b a b a q 0 q1 b q2 b q3 q4 a b a a,b q 5 b a a a,b a b a q 0 q1 b q2 b q3 q4 a b a a,b q 5 b a a a,b a b a q 0 q1 b q2 b q3 q4 Input finished a b a a,b reject q 5 b a a a,b a b a q 0 q1 b q2 b q3 q4 Another Rejection a,b q 5 b a a a,b a b a q0 q1 b q2 b q3 q4 a,b q 5 b a a a,b a b a q0 q1 b q2 b q3 q4 reject Another Example a a b a a,b b a,b q0 q1 q2 a a b a a,b q b q a,b q 0 1 2 a a b a a,b q b q a,b q 0 1 2 a a b a a,b q b q a,b q 0 1 2 Input finished a a b a a,b accept q b q a,b q 0 1 2 Rejection Example b a b a a,b b a,b q0 q1 q2 b a b a a,b q b q a,b q 0 1 2 b a b a a,b q b q a,b q 0 1 2 b a b a a,b q b q a,b q 0 1 2 Input finished b a b a a,b b a,b q0 q1 q2 reject Languages Accepted by FAs FA M Definition: The language M contains all input strings acceMted by L M = { strings that bring to an accepting state} Example L M abba M a,b q 5 b a a,b a a b a q0 q1 b q2 b q3 q4 accept Example L M ,ab,abba M a,b q 5 b a a a,b a b a q0 q1 b q2 b q3 q4 accept accept accept Example L M {a b:n 0} a a,b a,b q0 b q1 q2 accept trap state Example L M = { all strings with prefab } a,b q0 a q1 b q2 b a accept q3 a,b Example L M = { all strings without substring 001 } 1 0 0,1 1 0 1 0 00 001 0 Example L(M) awa :w a,b * a b b a q0 q2 q3 b a q4 a,b Regular Languages Definition: A languageL is regular if there is FA M such that L L M Observation: All languages accepted by FAs form the family of regular languages Examples of regular languages: abba ,ab,abba n awa :w a,b * {a b:n 0} { all strings with preab} { all strings without substr001 } There exist automata that accept these Languages. Non-Deterministic Finite Automata Nondeterministic Finite Automato(NFA) Alphabet ={a} a q1 q2 a q 0 a q3 Alphabet ={a} Two choices a q1 q2 a q 0 a q3 Alphabet ={a} Two choices a q1 q2 No transition a q 0 a q3 No transition First Choice a a a q1 q2 a q 0 a q3 First Choice a a a q1 q2 a q 0 a q3 First Choice a a a q1 q2 a q 0 a q3 First Choice a a All input is consumed a q1 q 2 “accept” a q 0 a q 3 Second Choice a a a q1 q 2 a q 0 a q3 Second Choice a a a q1 q 2 a q 0 a q3 Second Choice a a a q1 q2 a q 0 a No transition: q3 the automaton hangs Second Choice a a Input cannot be consumed a q1 q 2 a q 0 a q 3 “reject” An NFA accepts a string: when there is a computation of the NFA that accepts the string There is a computation: all the input is consumed and the automaton is in an accepting state Example aa is accepted by the NFA: “accept” q a q q1 a q2 a 1 2 a q0 a q0 a q 3 q3 “reject” because this computation accepts aa Rejection example a a q1 q2 a q 0 a q3 First Choice a a q1 q2 a q 0 a q3 First Choice a “reject” a q1 q2 a q 0 a q3 Second Choice a a q1 q2 a q 0 a q3 Second Choice a a q1 q2 a q 0 a q3 Second Choice a a q1 q2 a q 0 a q3 “reject” An NFA rejects a string: when there is no computation of the NFA that accepts the string. For each computation: • All the input is consumed and the automaton is in a non final state OR • The input cannot be consumed Example a is rejected by the NFA: “reject” q1 a q2 q a q a a 1 2 q0 a q0 a q3 “reject” q3 All possible computations lead to rejection Rejection example a a a a q1 q 2 a q 0 a q3 First Choice a a a a q1 q 2 a q 0 a q3 First Choice a a a a q1 q2 a q 0 a No transition: the automaton hangs q3 First Choice a a a Input cannot be consumed a q1 q 2 “reject” a q 0 a q 3 Second Choice a a a a q1 q 2 a q 0 a q3 Second Choice a a a a q1 q 2 a q 0 a q3 Second Choice a a a a q1 q2 a q 0 a No transition: q3 the automaton hangs Second Choice a a a Input cannot be consumed a q1 q 2 a q 0 a q 3 “reject” aaa is rejected by the NFA: “reject” q1 a q2 q1 a q2 a a q q 0 a 0 a q3 q 3 “reject” All possible computations lead to rejection Language accepted: L {aa} a q1 q2 a q 0 a q3 One path from q t0 an accepting state suffices q wL M w i qk q0 w w q j Lambda Transitions q0 a q1 q2 a q3 a a q0 a q1 q2 a q3 a a q0 a q1 q2 a q3 (read head does not move) a a q0 a q1 q2 a q3 a a q0 a q1 q2 a q3 all input is consumed a a “accept” q0 a q1 q2 a q3 String aa is accepted Rejection Example a a a q0 a q1 q2 a q3 a a a q0 a q1 q 2 a q3 (read head doesn’t move) a a a q0 a q1 q2 a q3 a a a q0 a q1 q2 a q3 No transition: the automaton hangs Input cannot be consumed a a a “reject” q0 a q1 q2 a q3 String aaa is rejected Language accepted: L {aa} q0 a q1 q2 a q3 Another NFA Example q a q1 b q2 q3 0 a b q a q1 b q2 q 3 0 a b q a 1 b q2 q 3 0 a b q a q1 b q2 q 3 0 a b “accept” q a q1 b q2 q3 0 Another String a b a b q a q b q q 0 1 2 3 a b a b q a q b q q 0 1 2 3 a b a b q a q b q q 0 1 2 3 a b a b q a q b q q 0 1 2 3 a b a b q a q b q q 0 1 2 3 a b a b q a q b q q 0 1 2 3 a b a b q a q b q q 0 1 2 3 a b a b “accept” q a q b q q 0 1 2 3 Language accepted L ab, abab, ababab, ... ab a q b q q q0 1 2 3 Another NFA Example 0 0,1 q0 q1 q2 1 Language accepted { } L(M) = λ, 10, 1010, 101010, ... = 10 * 0 0,1 q0 q1 q2 1 (redundant state) Remarks: •The symbol never appears on the input tape Theorem: Languages Regular accepted by NFAs Languages Languages accepted by FAs NFAs and FAs have the same computation power We can show: Languages accepted Regular by NFAs Languages Languages accepted Regular Languages by NFAs Proof-Step 1 Languages Regular accepted Languages by NFAs Proof:Every FA is trivially an NFA Any languageL accepted by a FA is also accepted by an NFA Proof-Step 2 Languages Regular accepted Languages by NFAs Proof: Any NFA can be converted to an equivalent FA Any language accepted by an NFA is also accepted by a FA Properties of Regular Languages For regular languagesL and L : 1 2 Union: L1 L 2 Concatenation: L1 2 Are regular Star: L1* Languages Reversal: L1R Complement: L 1 Intersection: L1 L 2 We say: Regular languages arclosed under Union: L1 L 2 Concatenation: L1 2 Star: L1* Reversal:L1R Complement: L 1 Intersection: L1 L 2 Non-regular languages {a b : n 0} Non-regular languages {vv : v{a,b}*} Regular languages a*b b*c a bc(a b)* etc... How can we prove that a language L is not regular? Prove that there is no DFA that accepts L Problem: this is not easy to prove Solution: the Pumping Lemma !!!

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

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

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