cs3102: Theory of Computation (aka cs302: Discrete ...

cs3102: Theory of Computation Class 7: Context-Free Languages Spring 2010 University of Virginia David Evans Menu Nondeterministic PDAs Reviewing Machine Models of Computing Linguistic Models of Computing DPDA Recap: DFA/ + Stack

q0 b, + a, + , $ q1 b, +

q2 , $ , $ Processing: aabb q3 Input aab

b aab b aab b aab b aab b

aab b aab b State q0 q1

q1 q1 q2 q2 q3 Stack

$ +$ ++$ +$ $

Adding Nondeterminism a a a Regular Languages Regular Languages Configuration: one state Configuration: set of states

DFA NFA What does it mean to add nondeterminism to a DPDA? Adding Nondeterminism to DPDA a, hp ht a, hp ht a, hp ht

Languages recognized: ? Configuration: one state + one stack DPDA NPDA Adding Nondeterminism to DPDA a, hp ht a, hp ht

a, hp ht Languages recognized: ? Configuration: one state + one stack DPDA Languages recognized: ? + ? Configuration: set of pairs NPDA

Example q0 , $ a, A q1 , b, B Now the -transition is optional: can be multiple transition is optional: can be multiple

possible edges for a state on a (a, h) input. a, A q2 b, B , $ q3 Acceptance: NPDA accepts w when:

(q0; w; ) ! (qf ; s) ^qf 2 F Accepting State Model (q0;w; ) ! (q; ) Empty Stack Model Is the set of languages accepted by NPDAs with each model the same? L(NPDA/Empty Stack) L(NPDA/Accepting)

L(NPDA/Empty Stack) L(NPDA/Accepting) q3 q8 , , qx , qstackCl

eaner ; h 2 ! L(NPDA/Accepting) L(NPDA/Empty Stack) L(NPDA/Accepting) L(NPDA/Empty Stack) q0 qk qz

qj , $ , $ q+ , $ qA Open (for us) Questions

L(DPDA/Accepting) =? L(DPDA/Empty Stack) Why dont the proofs for NPDAs work for DPDAs? Are NPDAs more powerful than DPDAs? (will answer next week) What languages cannot be recognized by an NDPDA? (will answer next week) Instead of answering these now, well introduce a different model and show it is equivalent to NPDA

Machine Models Yes! ababbaabbaba Kleene Machine flickr cc: markhillary Stephen Kleene* (1909-transition is optional: can be multiple 1994) Kleeneliness is next to Gdeliness Modeling Human Intellect

Turing Machine (Alan Turing, 1936) Modeling Human Computers Finite Automata 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, 1956 Our 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, 1956 Noam Chomsky I dont know anybody whos ever

read a Chomsky book, He does not write page turners, he writes page stoppers. There are a lot of bent pages in Noam Chomskys books, and they are usually at about Page 16. Alan Dershowitz I must admit to taking a copy of Noam Chomskys Syntactic Structures along 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 programmers 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 Knuth Modeling Language Generative Grammar

match replacement Modeling Language S NP VP NP N N AdjP N AdjP Adj Adj Adj N N VP V V V AdvP V V AdvP Adv

Adv Adv N ideas V sleep Adj Colorless Adj green Adv furiously Generative Grammars S NP VP NP Adj N VP V Adv

S NP VP NP Adj NP VP V Adv Adj Colorless Adj green N ideas V sleep Adv furiously Adj Colorless Adj green N ideas

V sleep Adv furiously How many sentences can S produce? How many sentences can S produce? S NP VP NP Adj NP NP N VP V Adv

Adj Colorless Adj green N ideas V sleep Adv furiously How many sentences can S produce? Recursion 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 Has It, and How Did It Evolve?, Science, Nov 2002 Steven Pinker and Ray Jackendoff (2004): its not just recursion... Kanzi and Sue Savage-transition is optional: can be multiple Rumbaugh Kanzis Language

Languages Modeling Computing Machines: String is in the language if machine accepts that input string. Power of a machine type is defined by the set of languages it can recognize. Generative grammars: String is in the language if grammar can produce that input string. Power of a grammar type is defined by the set of languages it can recognize. NPDA Languages DPDA Languages Regular

Languages Can be recognized by some DFA s Finite Languages All Languages Can we define types of grammars that correspond to each class? Finite Languages Finite Languages

Machine: simple lookup table DFA with no cycles Grammar: grammar with no cycles A terminals Regular Languages Regular Languages Machine: DFA Grammar: Regular Grammar

Finite Languages A aB Aa Hint: PS2, Problem 9 L(DFA) L(Regular Grammar) Context-transition is optional: can be multiple Free Grammars A BCD Match: one nonterminal Replacement: any sequence of

terminals and nonterminals Can a CFG generate the language anbn? { w | w contains more as than bs } Context-transition is optional: can be multiple Free Languages NPDA Languages Regular Languages Finite Languages

Machine: NPDA Grammar: Context-Free Grammar A BCD Left side: one nonterminal Replacement: any sequence of terminals and nonterminals L(NDPDA) L(CFG) 1. L(NDPDA) L(CFG) Detailed Proof: Sipser, Section 2.2

L(NDPDA) L(CFG) 2. L(CFG) L(NDPDA) Detailed Proof: Sipser, Section 2.2 More Powerful Grammars Con tesxt -Fre Lan e gua

ges Context-Free Grammar A BCD Aa Context-Sensitive Grammar XAY XBCDY Unrestricted Grammar XAY BCD Recap Questions How can you prove a How can you prove a grammar is regular?

grammar is context-free? How can you prove a How can you prove a language is regular? language is context-transition is optional: can be multiple free? How can you prove a How can you prove a language is not language is not context-transition is optional: can be multiple regular? free? Charge PS2 is due Tuesday Human Languages

Are they finite, regular, context-transition is optional: can be multiple free, context-transition is optional: can be multiple sensitive? (Is the human brain a DFA, PDA, etc. or something entirely different?) Next week: Non-Context-Free Languages Parsing, Applications of Grammars

Recently Viewed Presentations

  • Georgia and the American Experience

    Georgia and the American Experience

    The Fall of Fort Pulaski. More than 100 battles or skirmishes in Georgia; 92 happened in 1864 during the Atlanta and Savannah campaigns. First battle, April 10, 1862, was at all-brick Fort Pulaski, near Tybee Island. Rifled cannon used by...
  • Smoke Free Campus Team briefing What is a

    Smoke Free Campus Team briefing What is a

    The implementation of a smoke-free environment is an important initiative and Box Hill Institute is using a variety of media to communicate this message, including: signage around the campus and perimeter student diary and StudentWeb website email updates to staff...
  • FST 108: PCardholder Training - usf.edu

    FST 108: PCardholder Training - usf.edu

    Where Can I Use My PCard? The USF System PCard can be used at any business that accepts Visa. A PCard may be used: In person at the merchant location. Over the phone. Online. All purchases must be in accordance...
  • The Great Gatsby - St. Barnabas High School

    The Great Gatsby - St. Barnabas High School

    What is your reaction to Gatsby's funeral turnout? What is your opinion of Henry Gatz? What did you like most and least about the ending of the novel? Are you surprised that Nick is moving back to the mid-west? Nick...
  • Control of Gene Expression - Bio Resource Site

    Control of Gene Expression - Bio Resource Site

    Control of Gene Expression If all cells have the same genome, why are they so different from each other? Two levels of metabolic control Feedback inhibition - quick response to short term fluctuations in amount of required substance Operon model...
  • How do associations represent their members?

    How do associations represent their members?

    Similar to how the Iroquois elected Hoyaneh to act as representatives at the grand council. Which right and freedom from the Canadian charter of rights and freedoms guarantees that associations such as the ACFA can exist? A monument to Alberta...
  • Vodafone PowerPoint template - Netcom

    Vodafone PowerPoint template - Netcom

    PPTP-Client. GRE. The Point-to-Point Tunnelling Protocol (PPTP) is a method for implementing virtual private networks using a TCP and GRE tunnel to encapsulate PPP packets. PPTP operates on Layer 2 of the OSI model and is included on Windows computers.
  • Les lésion s élémentaires de la cellule

    Les lésion s élémentaires de la cellule

    la matrice mitochondriale devient très dense. la mitochondrie passe d'une phase normale phase de contraction. Le gonflement de grande amplitude: Augmentation de la perméabilité de la CI expansion de la CI avec déplissement et même fragmentation des crêtes.