DOC PREVIEW
UMD CMSC 132 - Regular Expressions & Automata

This preview shows page 1-2-3-4-5 out of 16 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 16 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 16 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 16 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 16 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 16 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 16 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1Regular Expressions & Automata Nelson Padua-PerezChau-Wen TsengDepartment of Computer ScienceUniversity of Maryland, College ParkComplexity to ComputabilityJust looked at algorithmic complexityHow many steps requiredAt high end of complexity is computabilityDecidableUndecidable2Complexity to ComputabilityApproach complexity from different directionLook at simple models of computationRegular expressionsFinite automataTuring MachinesOverviewRegular expressionsNotationPatternsJava supportAutomataLanguagesFinite State MachinesTuring MachinesComputability3Regular Expression (RE)Notation for describing simple string patternsVery useful for text processingFinding / extracting pattern in textManipulating stringsAutomatically generating web pagesRegular ExpressionRegular expression is composed ofSymbolsOperators Concatenation ABUnion A | BClosure A*4DefinitionsAlphabetSet of symbols ΣExamples ⇒ {a, b}, {A, B, C}, {a-z,A-Z,0-9}…StringsSequences of 0 or more symbols from alphabetExamples ⇒ ε, “a”, “bb”, “cat”, “caterpillar”…LanguagesSets of stringsExamples ⇒ ∅, {ε}, {“a”}, {“bb”, “cat”}…empty stringMore FormallyRegular expression describes a language over an alphabetL(E) is language for regular expression ESet of strings generated from regular expressionString in language if it matches pattern specified by regular expression5Regular Expression ConstructionEvery symbol is a regular expressionExample “a”REs can be constructed from other REs usingConcatenationUnion |Closure *Regular Expression ConstructionConcatenationA followed by BL(AB) = { ab | a ∈ L(A) AND b ∈ L(B) }Examplea{“a”}ab{“ab”}6Regular Expression ConstructionUnionA or BL(A | B) = { a | a ∈ L(A) OR a ∈ L(B) }Examplea | b{“a”, “b”}Regular Expression ConstructionClosureZero or more AL(A*) = { a | a = ε OR a ∈ L(A) OR a ∈ L(A)L(A)… }Examplea* {ε, “a”, “aa”, “aaa”, “aaaa” …}(ab)*c{“c”, “abc”, “ababc”, “abababc”…}7Regular Expressions in JavaJava supports regular expressions In java.util.regex.*Applies to String class in Java 1.4Introduces additional specification methodsSimplifies specificationDoes not increase power of regular expressionsCan simulate with concatenation, union, closureRegular Expressions in JavaConcatenationab “ab”(ab)c “abc”Union ( bar | or square brackets [ ] )a | b “a”, “b”[abc] “a”, “b”, “c”Closure (star *)(ab)* ε, “ab”, “abab”, “ababab” …[ab]* ε, “a”, “b”, “aa”, “ab”, “ba”, “bb” …8Regular Expressions in JavaOne or more (plus +)(a)+ One or more “a”sRange (dash –)[a–z] Any lowercase letters[0–9] Any digitComplement (caret ^ at beginning of RE)[^a] Any symbol except “a”[^a–z] Any symbol except lowercase lettersRegular Expressions in JavaPrecedenceHigher precedence operators take effect firstPrecedence orderParentheses ( … )Closure a* b+Concatenation abUnion a | bRange [ … ]9Regular Expressions in JavaExamplesab+ “ab”, “abb”, “abbb”, “abbbb”…(ab)+ “ab”, “abab”, “ababab”, …ab | cd “ab”, “cd”a(b | c)d “abd”, “acd”[abc]d “ad”, “bd”, “cd”When in doubt, use parenthesesRegular Expressions in JavaPredefined character classes[.] Any character except end of line[\d] Digit: [0-9][\D] Non-digit: [^0-9][\s] Whitespace character: [ \t\n\x0B\f\r][\S] Non-whitespace character: [^\s][\w] Word character: [a-zA-Z_0-9][\W] Non-word character: [^\w]10Regular Expressions in JavaLiterals using backslash \Need two backslashJava compiler will interpret 1stbackslash for StringExamples\\] “]”\\. “.”\\\\ “\”4 backslashes interpreted as \\ by Java compilerUsing Regular Expressions in Java1. Compile patternimport java.util.regex.*;Pattern p = Pattern.compile("[a-z]+");2. Create matcher for specific piece of text Matcher m = p.matcher("Now is the time");3. Search textBoolean found = m.find();Returns true if pattern is found in text11Using Regular Expressions in JavaIf pattern is found in textm.group() ⇒ string found m.start() ⇒ index of the first character matchedm.end() ⇒ index after last character matchedm.group() is same as substring(m.start(), m.end())Calling m.find() againStarts search after end of current pattern matchIf no more matches, return to beginning of stringComplete Java ExampleCodeOutputow – is – the – time –import java.util.regex.*;public class RegexTest {public static void main(String args[]) {Pattern p = Pattern.compile(“[a-z]+”);Matcher m = p.matcher(“Now is the time”);while (m.find()) {System.out.print(m.group() + “ – ”);} } }12Language RecognitionAccept string if and only if in language Abstract representation of computationPerforming language recognition can beSimpleStrings with even number of 1’sHardStrings representing legal Java programsImpossible!Strings representing nonterminating Java programsAutomataSimple abstract computersCan be used to recognize languagesFinite state machineStates + transitionsTuring machineStates + transitions + tape13Finite State MachineStatesStartingAcceptingFinite number allowedTransitionsState to stateLabeled by symbolL(M) = { w | w ends in a 1}q1q20101Start StateAccept StateaFinite State MachineOperations Move along transitions based on symbol Accept string if ends up in accept stateReject string if ends up in non-accepting stateq1q20101“011” Accept“10” Reject14Finite State MachinePropertiesPowerful enough to recognize regular expressionsIn fact, finite state machine ⇔ regular expressionLanguages recognized by finite state machinesLanguages recognized by regular expressions1-to-1 mappingTuring MachineDefined by Alan Turing in 1936Finite state machine + tapeTapeInfinite storageRead / write one symbol at tape headMove tape head one space left / rightTape Head… …q1q2010115Turing MachineAllowable actionsRead symbol from current squareWrite symbol to current squareMove tape head leftMove tape head rightGo to next stateTuring Machine* 1 0 0 1 0 *……HALTNo move**MOVINGMOVINGLeft10MOVINGMOVINGLeft01MOVINGMOVINGLeft**STARTNew state to enterDirection to MoveValue to WriteCurrent ContentCurrent StateTape Head16Turing MachineOperationsRead symbol on current squareSelect action based on symbol & current stateAccept string if in accept stateReject string if halts in non-accepting stateReject string if computation does not terminateHalting problemIt is undecidable in general


View Full Document

UMD CMSC 132 - Regular Expressions & Automata

Documents in this Course
Notes

Notes

8 pages

Recursion

Recursion

12 pages

Sorting

Sorting

31 pages

HTML

HTML

7 pages

Trees

Trees

19 pages

HTML

HTML

18 pages

Trees

Trees

19 pages

Honors

Honors

19 pages

Lecture 1

Lecture 1

11 pages

Quiz #3

Quiz #3

2 pages

Hashing

Hashing

21 pages

Load more
Download Regular Expressions & 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 Regular Expressions & 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 Regular Expressions & 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?