Comp 481

Comp 481

Lexical Analysis Uses formalism of Regular Languages Regular Expressions Deterministic Finite Automata (DFA) Non-deterministic Finite Automata (NDFA) RE NDFA DFA minimal DFA (F)Lex uses RE as input, builds lexor 1

DFAs: Formal Definition DFA M = (Q, , , q0, F) Q = states finite set = alphabet finite set = transition function function in Q Q q0 = initial/starting state q0 Q F = final states FQ 2 DFAs: Example strings over {a,b} with next-to-last symbol = a

a b a a ab a a b b aa b

b a b a b ba a bb b 3 Nondeterministic Finite Automata

Nondeterminism implies having a choice. Multiple possible transitions from a state on a symbol. (q,a) is a set of states : Q Pow(Q) Can be empty, so no need for error/nonsense state. Acceptance: exist path to a final state? I.e., try all choices. Also allow transitions on no input: : Q ( {}) Pow(Q) 4 NFAs: Formal Definition NFA M = (Q, , , q0, F) Q = states a finite set = alphabet

a finite set = transition function a total function in Q ( {}) Pow(Q) q0 = initial state q0 Q F = final states FQ 5 NFAs: Example strings over {a,b} with next-to-last symbol = a a

a a Loop until we guess which is the next-to-last a. 6 NFAs: Example strings over {0,1,2} having (either 0-or-more 0s or 0-or-more 1s) followed by 0-or-more 2s 0 2 0s

1 1s 2s 7 Regular Expressions Regular expression (over )

a where a r+r r r r* where r,r regular (over ) Notational shorthand: r0 = , ri = rri-1 r+ = rr* 8

RE NFA Defined inductively on structure of RE. This construction produces NFA with single final state. 6 cases: , , a, r+r, rr, r* 9 RE NFA: q0 qf

Accepts nothing since no edge to final state. 10 RE NFA: q0 11 RE NFA: a q0 a qf 12

RE NFA: r+r q0 qf q0 qf q0 qf

edges guess whether to use r or r. 13 RE NFA: rr q0 q0 qf q0

qf qf Could conflate q0 with q0, qf with qf. 14 RE NFA: r* q0 q0

qf qf Can loop r as many times as desired or skip it. 15 RE NFA: Example (0+01)* 0

0 1 16

RE NFA: Notes Most constructions produce very large NFAs. Not optimal for size. But easy to construct. 17 NFA -> DFA Subset Construction Complicated but well described in the text

Section 3.7.1 (pp 152-155), Algorithm 3.20 (2nd edition) In section 3.6 (pp 116-121) in 1st edition 18 Minimizing DFA Partition states of DFA, D, into two sets, final states, and non-final states. Continue until no more partitions are

needed For each partition, P, split the DFA states of P so that, for each subpartition, all DFA states in that partition have the same transition for each input symbol, x. 19

Recently Viewed Presentations

  • PowerPoint-Präsentation

    PowerPoint-Präsentation

    ARIS TRAINING VIDEOS. This video series is an in-depth case study of the business processes at Frankfurt Airport. Each video discusses one part of the ARIS House.
  • Naval Radiation Safety Committee Expenditure of Depleted Uranium

    Naval Radiation Safety Committee Expenditure of Depleted Uranium

    Chronology of Events… Continued Vieques Island, Puerto Rico Inner Training Range North Convoy Vieques Inner Range 25 mm PGU-20/U NALC A979 Armor Piercing Incendiary (API) 148 grams DU Causes of Incident Personnel did not follow standard protocol to check all...
  • WATER HANDLING OPERATIONS Unit 4C - Foam and

    WATER HANDLING OPERATIONS Unit 4C - Foam and

    Objectives. Identify various operational components of the FoamPro® 1600/1601 and WaterousAquis 1.5. Demonstrate the ability to set up, run, have foam solution pumped to a nozzle person, and shut down a foam proportioner.
  • Inheritance and Class Hierarchies - UMass Amherst

    Inheritance and Class Hierarchies - UMass Amherst

    Lists and the Collection Interface Based on Koffmann and Wolfgang Chapter 4 Chapter Outline The List interface Writing an array-based implementation of List Linked list data structures: Singly-linked Doubly-linked Circular Implementing List with a linked list Chapter Outline (2) The...
  • Conquering the Comma Purdue OWL staff Brought to

    Conquering the Comma Purdue OWL staff Brought to

    * Rationale: Welcome to "Conquering the Comma." This presentation is designed to acquaint your students with the rules of comma usage, including placement in compound sentences, after introductory elements, with dependent phrases and clauses, around nonessential elements, in a series,...
  • Darwin and The Theory of Evolution

    Darwin and The Theory of Evolution

    Darwin's Theory of Evolution by Natural Selection. Darwin spent many years thinking about the work of Lamarck, Lyell, and Malthus, what he had seen on his voyage, and artificial selection. What did all this mean? How did it all fit...
  • 0 2019-01-12 C h in a U n

    0 2019-01-12 C h in a U n

    2019-01-12. Primärenergianvändning per capita (1980-2016, Mbtu) Källa: Energy Information Administration, Energiföretagen
  • 5th Annual Conference on Research in University Colleges

    5th Annual Conference on Research in University Colleges

    Program Selection Kwantlen has focused on Bachelor of Arts Degree programs for the following reasons High student demand Employer demand Relatively low resource and delivery costs Faculty expertise External Accreditation Existing Bachelor of Arts Degrees Bachelor of Arts, Applied Psychology...