DOC PREVIEW
UMD CMSC 330 - Examples of REs & Finite Automata

This preview shows page 1-2-3 out of 9 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CMSC 330: Organization of Programming LanguagesSlide 2Slide 3Slide 4Describing Regular ExpressionsCreating Regular ExpressionsSlide 7Creating DFACreating NFACMSC 330: Organization of Programming LanguagesDiscussion Section, 2/11Examples of REs & Finite AutomataWhat do we know about REs?•The Formal Vocab–Symbol–Alphabet–String–Language•The Special Symbol: ε•The Formal Operations–Concatenation, e.g. /ab/–Union, e.g. /a|b/–Kleene Closure, e.g. a*ha(ha)*More About REs•Operator Precedence–Kleene closure * > concatenation > union |–Like arithmetic, use parentheses to override•How’d we get from here to DFA again?Anything but DFA!!!!CMSC 330 5Describing Regular Expressions●0(0|1)*0●All strings beginning and ending in 0●((ε|0)1*)*●All strings ●(0|1)*0(0|1)(0|1)●All strings with 0 as third digit from rightCMSC 330 6Creating Regular ExpressionsFor all strings of 0’s and 1’s that…a) Begin in 1–1(0|1)*a) End in 1–(0|1)*1a) Contain 00–(0|1)*00(0|1)*a) Do not contain 00–(01|1)*(ε|0)Finite Automata•We can further formalize regular expressions as finite automata.–Why? To reason about them.•What are the choices?–Deterministic–Non-deterministic•Why have two choices?•What are the differences?CMSC 330 8Creating DFAFor all strings of 0’s and 1’s that…a) Begin in 1b) End in 1c) Contains 00d) Do not contain 00100,10110 0110,10 0110,1Swap final / non-final states!CMSC 330 9Creating NFAFor all strings of 0’s and 1’s that…a) Begin in 1b) End in 1c) Contain 00d) Do not contain 0010,110 00,100,10,11εεε0Based on regular


View Full Document

UMD CMSC 330 - Examples of REs & Finite Automata

Documents in this Course
Exam #1

Exam #1

6 pages

Quiz #1

Quiz #1

2 pages

Midterm 2

Midterm 2

12 pages

Exam #2

Exam #2

7 pages

Ocaml

Ocaml

7 pages

Parsing

Parsing

38 pages

Threads

Threads

12 pages

Ruby

Ruby

7 pages

Quiz #3

Quiz #3

2 pages

Threads

Threads

7 pages

Quiz #4

Quiz #4

2 pages

Exam #2

Exam #2

6 pages

Exam #1

Exam #1

6 pages

Threads

Threads

34 pages

Quiz #4

Quiz #4

2 pages

Threads

Threads

26 pages

Exam #2

Exam #2

9 pages

Exam #2

Exam #2

6 pages

Load more
Download Examples of REs & Finite Automata
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Examples of REs & Finite Automata and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Examples of REs & Finite Automata 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?