CFL Big Picture

Please download to get full document.

View again

of 12
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 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
  • 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
  • Acceptance
  • Context 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 derivations
  • Push down automata
  • Use of instantaneous descriptions (IDs) and the relation |- between IDs
  • Acceptance by final state
  • Acceptance by empty stack
  • Algorithms
  • We 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
  • Parsing
  • We 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)
  • Properties
  • We saw that Regular Languages have many properties
  • Closure properties
  • Union
  • Kleene – star
  • Intersection
  • Complement
  • Reversal
  • Difference
  • CFL have fewer properties
  • Closure properties
  • Union
  • Kleene – star
  • Concat
  • But we do have the intersection between CFL and RL produces a CFL
  • Proving some language is not CF
  • Pumping 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 Pump
  • A 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
    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