All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Information Report

Category:
## Documents

Published:

Views: 86 | Pages: 12

Extension: PDF | Download: 0

Share

Description

CFL Big Picture. Context Free Languages Conclusion. We have studied the class of context free languages (CFL) We saw many different ways to express a CFL Context Free Grammars Context Free Expressions. Things like (mu x . a x a) Push Down Automata

Transcript

CFL Big PictureContext Free Languages ConclusionWe have studied the class of context free languages (CFL) We saw many different ways to express a CFL Context Free Grammars Context Free Expressions. Things like (mu x . a x a) Push Down Automata We showed that some were equally expressive We need non-deterministic PDA to express Context Free Grammars Recall the construction of the PDA had only one state, and possible several transitions on the same Non-terminal. Some were easier to use than others to describe some languages AcceptanceContext free grammars The language of the CFG , G, is the setL(G) = {wÎT* | S Þ* w} whereS is the start symbol of GÞ is the single step relation between derivationsPush down automata Use of instantaneous descriptions (IDs) and the relation |- between IDs Acceptance by final state Acceptance by empty stack AlgorithmsWe studied algorithms to transform one description into another Context Free Grammar to PDA (Alg 12.7 pg 770) PDA into Context Free Grammar (Alg 12.8 pp771-772) We studied how to transform grammars To remove ambiguity (layering) Non-ambiguous languages can have ambiguous grammars Some languages are inherently ambiguous. To remove left recursion by factoring ParsingWe studied how to accept CFL by using parsing methods based upon context free grammars Top down methods - LL(1) Recursive descent Predictive parsers Bottom up methods – LR(1) PropertiesWe saw that Regular Languages have many properties Closure properties Union Kleene – star Intersection Complement Reversal Difference CFL have fewer propertiesClosure properties Union Kleene – star Concat But we do have the intersection between CFL and RL produces a CFL Proving some language is not CFPumping lemma for CF languages Let L be a CFL. Then there exists a number n (depending on L) such that every string w in L of length greater than n contains a CFL pump. Context Free PumpA CFL pump consists of two non-overlapping substrings that can be pumped simultaneously while staying in the language. Precisely, two substrings u and v constitute a CFL pump for a string w of L ( |w| > m) when uv¹L(which means that at least one of u or v is not empty) And we can write w=xuyvz, so that for every i³ 0 xuiyvizÎ L The Regular Worlddata DFA q s = DFA { states :: [q], symbols :: [s], delta :: q -> s -> q, start :: q, final :: [q]}Lift delta funSubset Constructiondata NFA q s = NFA { states :: [q], symbols :: [s], delta :: q -> s -> [q], start :: q, final :: [q]}DFANFAdata GNFA q s = GNFA { states :: [q], symbols :: [s], delta :: q -> q -> RegExp s, start :: q, final :: q }Delta fun liftingTransition to productionGenNFARegGrame-removaldata RegGram v t = RegGram { nonTerm :: [v] , term :: [t] , prod :: [Prod v t] , start :: v }data RegExp a = Lambda | Empty | One a | Union (RegExp a) (RegExp a) | Cat (RegExp a) (RegExp a) | Star (RegExp a)State Eliminationdata NFAe q s = NFAe { states :: [q], symbols :: [s], delta :: q -> Maybe s -> [q], start :: q, final :: [q]}eNFARegExpVia GenNFA by RegExpdecompostionThe Context Free WorldMu instantiationMu AbstractionContext Free ExpressionsContext Free Grammarsdata CFGram n t = CFGram { nonTerm :: [n] , terms :: [t] , prod :: [(n,[Sym n t])] , start :: n }data CfExp a = Lambda | Empty | One a | Union (CfExp a) (CfExp a | Cat (CfExp a) (CfExp a) | Mu Int (CfExp a) | V IntDeterministic PDAAlg 12.7Alg 12.8data PDA q s z = PDA { states :: [q], symbols :: [s],stacksym :: [z], delta :: [(q,Maybes,z,[(q,[z])])], start :: q, final :: [q]}Non-deterministic PDAThe Larger WorldanbncnRegular LanguagesanbmContext Free Languagesanbnpalindromes

Recommended

35 pages

18 pages

10 pages

19 pages

Related Search

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks

SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...Sign Now!

We are very appreciated for your Prompt Action!

x