DOC PREVIEW
UVA CS 302 - Context-Free Languages

This preview shows page 1-2 out of 6 pages.

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

Unformatted text preview:

1David Evanshttp://www.cs.virginia.edu/evanscs302: Theory of ComputationUniversity of VirginiaComputer ScienceLecture 8: Lecture 8: ContextContext--Free Free LanguagesLanguages2Lecture 8: LanguageMenu• Review Machine Models of Computing• Linguistic Model of Computing• Challenge Problem Near-Solution -Liuyi (Eric) Zhang• Context-Free Grammars3Lecture 8: LanguageDeterministic Machine Models010110101101010101“Yes”or“No”Memory Machine LanguagesFinite States DFA Regular+ Stack DPDA [this week]+ Tape TM [later]4Lecture 8: Language010110101101010101“Yes”or“No”Nondeterministic Machine ModelsMemory Machine LanguagesFinite States NFA Regular+ Stack NDPDA [this week]+ Tape NDTM [later]5Lecture 8: LanguageWhere did these models come from?6Lecture 8: LanguageModeling Human Intellect• Turing Machine (Alan Turing, 1936)– Modeling Human Computers• DFAs– McCulloch and Pitts, “A logical calculus of the ideas immanent in nervous activity”, 1943– S. C. Kleene, Representation of Events in Nerve Nets and Finite Automata, 1956– Claude Shannon and John McCarthy, Automata Studies, 195627Lecture 8: LanguageOut theoretical objective is not dependent on the assumptions fitting exactly. It is a familiar strategem of science, when faced with a body of data too complex to be mastered as a whole, to select some limited domain of experiences, some simple situations, and to undertake to construct a model to fit these at least approximately. Having set up such a model, the next step is to seek a thorough understanding of the model itself.S. C. Kleene, Representation of Events in Nerve Nets and Finite Automata, 19568Lecture 8: LanguageLanguage-Based Models of Computation9Lecture 8: LanguageNoam Chomsky (born 1928), MIT Linguistics Professor and Leftist Political Activist10Lecture 8: LanguageHugo Chávez at theUnited Nations (20 Sept 2006)11Lecture 8: LanguageI don’t know anybody who’s ever read a Chomsky book, He does not write page turners, he writes page stoppers. There are a lot of bent pages in Noam Chomsky’s books, and they are usually at about Page 16.Alan Dershowitz12Lecture 8: Language“I must admit to taking a copy of Noam Chomsky’s Syntactic Structuresalong with me on my honeymoon in 1961. During odd moments, while crossing the Atlantic in an ocean liner and while camping in Europe, I read that book rather thoroughly and tried to answer some basic theoretical questions. Here was a marvelous thing: a mathematical theory of language in which I could use a computer programmer’s intuition! The mathematical, linguistic, and algorithmic parts of my life had previously been totally separate. During the ensuing years those three aspects became steadily more intertwined; and by the end of the 1960s I found myself a Professor of Computer Science at Stanford University, primarily because of work that I had done with respect to languages for computer programming.”Donald Knuth313Lecture 8: LanguageReplacement GrammarsLeft → RightAnything that matches the left side can be replacedby what is on the right side.Left and Right can be any sequence of variables (nonterminals) and symbols (terminals)14Lecture 8: LanguageRestricted Replacement GrammarsUnrestricted: α → β(left and right sides can be any sequence of symbols and variables)Context-Sensitive: αAβ → αγβ(A is a variable)Context-Free: A → αγβRegular: A → aB ; A → a15Lecture 8: LanguageExample Regular GrammarS → See AA → Spot BA → Jane BB → runB → jumpSABEndSeeSpotJanerun jumpHow many possible sentences?Why do we call it a RegularGrammar?16Lecture 8: LanguageKanzi and Sue Savage-Rumbaugh17Lecture 8: LanguageExample Regular GrammarS → See AA → Spot BA → Jane BB → runB → jumpB →→→→ and ASABEndSeeSpotJanerunjumpand18Lecture 8: LanguageCharles Yang419Lecture 8: LanguageRecursion = Human ?We hypothesize that faculty of language in the narrow sense (FLN) only includes recursion and is the only uniquely human component of the faculty of language. We further argue that FLN may have evolved for reasons other than language, hence comparative studies might look for evidence of such computations outside of the domain of communication (for example, number, navigation, and social relations). Marc Hauser, Noam Chomsky, Tecumseh Fitch, The Faculty of Language: What Is It, Who HasIt, and How Did It Evolve?, Science, Nov 2002Steven Pinker and Ray Jackendoff (2004): its not just recursion...20Lecture 8: LanguageChallenge ProblemLiuyi (Eric) Zhang21Lecture 8: LanguageProblem:Sort 1 million 32-bit integers22Lecture 8: LanguageReview: HeapsA heap is a “complete” binary tree, usually represented as an array:164 1014 7 9 32 8 116 14 10 8 7 9 3 2 4 1A =From David Luebke CS 432 Spring 2002 Slides23Lecture 8: LanguageSorting• Heap starts 32 bit before the 1stinteger• Max - Ordered Heap• Building Sorted List24Lecture 8: LanguageBit Sort• Sort bit by compare 8 bits with 011111112• Upper-to-Bottom bit sort525Lecture 8: LanguageContinue• Sort till the last bit• Bottom-up26Lecture 8: LanguageMemory27Lecture 8: LanguageCompare• Heap Sort– Requires ~ n log2n comparisons– 4 bytes to store integer• Bit Sort: – Requires ~ 32n comparisons– Memory to store (up to 33) memory addresses that separate the 1s and 0s28Lecture 8: LanguageChallenge Recap29Lecture 8: LanguageLanguage ClassesFiniteDescribed by a finite set,DFA with no cycles, Regular grammar with no recursionRegularDescribed by a DFA, NFA, Regular grammarContext-FreeDescribed by a NDPDA, Context-Free Grammar30Lecture 8: LanguageContext-Free GrammarA → αγβOne variable Any sequence of variables and terminalsWhy is it called “Context-Free”?631Lecture 8: LanguageExample 1S → 0S0S → 1S1S → ε32Lecture 8: LanguageExample 2Define a CFG that generates the language:{ w | w ∈ {0, 1}* and w has an equal number of 0s and 1s }33Lecture 8: LanguageReview Questions• How do you prove a grammar is context-free?• How do you prove a grammar is not context-free?• How do you prove a language is context-free?• How do you prove a language is not context-free?34Lecture 8: LanguageCharge• Return PS2 and PS2 Comments now• PS3 is posted on the course site (Due in 1 week, Feb 19)• Thursday:– Equivalence of NDPDAs and CFGs(sketch)– Non-Context-Free


View Full Document
Download Context-Free Languages
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 Context-Free Languages 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 Context-Free Languages 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?