×

### Let's log you in.

or

Don't have a StudySoup account? Create one here!

×

or

by: thersh

10

0

141

# FoCS Week 12 CSCI 2200

thersh
RPI

Get a free preview of these Notes, just enter your email below.

×
Unlock Preview

Notes from week 12 of class
COURSE
Foundations of Computer Science
PROF.
Petros Drineas
TYPE
Class Notes
PAGES
141
WORDS
KARMA
25 ?

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

#### 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 xx 2 compute x x f (x)  x3 temporary memory input memory x  2 CPU output memory Program memory compute xx 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 xx 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 xx 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 2a n abba v  b b b 1 2 m bbbaaa Concatenation wv  a1 2a bn 1 2 m abbabbbaaa w  a1 2a 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  35 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   abba0  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 abbL 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 :wL} 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: xL 1 yL 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 aabbaaabbbL 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 wL 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 bc(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!

×

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

Bentley McCaw University of Florida

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

Janice Dongeun University of Washington

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

Jim McGreen Ohio University

Forbes

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

Become an Elite Notetaker and start selling your notes online!
×

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