Models of Computation by Dr. Michael P. Frank, University of Florida Modified and extended by Longin Jan Latecki, Temple UniversityModeling ComputationEarly Models of Computation§11.1 – Languages & GrammarsComputers as Transition FunctionsLanguage Recognition ProblemVocabularies and SentencesGrammarsPhrase-Structure GrammarsProductionsLanguages from PSGsPSG Example – English FragmentProductions for our LanguageBackus-Naur FormA Sample Sentence DerivationAnother ExampleDerivabilityA Simple Definition of L(G)Language Generated by a GrammarGenerating Infinite LanguagesAnother exampleTypes of Grammars - Chomsky hierarchy of languagesDefining the PSG TypesClassifying grammarsRegular grammars (Type 3)Slide 26Context-Free Grammars (Type 2)Slide 28Slide 29Context-Sensitive Grammar (Type 1)Slide 31Models of Computationby Dr. Michael P. Frank, University of Florida Modified and extended by Longin Jan Latecki, Temple UniversityRosen 5Rosen 5thth ed., Ch. 11.1 ed., Ch. 11.1Modeling Computation•An algorithm:An algorithm:–A description of a computational procedure.A description of a computational procedure.•Now, how can we model the computer Now, how can we model the computer itself, and what it is doing when it carries itself, and what it is doing when it carries out an algorithm?out an algorithm?–For this, we want to model the abstract process For this, we want to model the abstract process of of computationcomputation itself. itself.Early Models of Computation•Recursive Function TheoryRecursive Function Theory–Kleene, Church, Turing, Post, 1930’sKleene, Church, Turing, Post, 1930’s•Turing Machines Turing Machines – Turing, 1936– Turing, 1936•RAM Machines RAM Machines – von Neumann, 1940’s– von Neumann, 1940’s•Cellular Automata Cellular Automata – von Neumann, 1950’s– von Neumann, 1950’s•Finite-state machines, pushdown automataFinite-state machines, pushdown automata–various people, 1950’svarious people, 1950’s•VLSI models VLSI models – 1970s– 1970s•Parallel RAMs, etc. Parallel RAMs, etc. – 1980’s– 1980’s§11.1 – Languages & Grammars•Phrase-Structure GrammarsPhrase-Structure Grammars•Types of Phrase-Structure GrammarsTypes of Phrase-Structure Grammars•Derivation TreesDerivation Trees•Backus-Naur FormBackus-Naur FormComputers as Transition Functions•A computer (or really any physical system) can be A computer (or really any physical system) can be modeled as having, at any given time, a specific state modeled as having, at any given time, a specific state ssSS from some (finite or infinite) from some (finite or infinite) state space state space SS..•Also, at any time, the computer receives an Also, at any time, the computer receives an input symbolinput symbol iiII and produces an and produces an output symboloutput symbol ooOO. . –Where Where II and and OO are sets of symbols. are sets of symbols.•Each “symbol” can encode an arbitrary amount of data.Each “symbol” can encode an arbitrary amount of data.•A computer can then be modeled as simply being a A computer can then be modeled as simply being a transition function transition function TT::SS××II → → SS××OO..–Given the old state, and the input, this tells us what the Given the old state, and the input, this tells us what the computer’s new state and its output will be a moment later.computer’s new state and its output will be a moment later.•Every model of computing we’ll discuss can be viewed Every model of computing we’ll discuss can be viewed as just being some special case of this general picture.as just being some special case of this general picture.Language Recognition Problem•Let a Let a language language LL be any set of some arbitrary objects be any set of some arbitrary objects ss which will be dubbed “sentences.”which will be dubbed “sentences.”–That is, the “legal” or “grammatically correct” sentences of the That is, the “legal” or “grammatically correct” sentences of the language.language.•Let the Let the language recognition problemlanguage recognition problem for for LL be: be:–Given a sentence Given a sentence ss, is it a legal sentence of the language , is it a legal sentence of the language LL? ? •That is, is That is, is ssLL??•Surprisingly, this simple problem is as general as our Surprisingly, this simple problem is as general as our very notion of computation itself! very notion of computation itself!Vocabularies and Sentences•Remember the concept of strings Remember the concept of strings ww of of symbols symbols ss chosen from an alphabet chosen from an alphabet ΣΣ??–An alternative terminology for this concept: An alternative terminology for this concept: •SentencesSentences σσ of of wordswords υυ chosen from a chosen from a vocabulary vocabulary VV..–No essential difference in concept or notation!No essential difference in concept or notation!•Empty sentence (or string): Empty sentence (or string): λλ (length 0) (length 0)•Set of all sentences over Set of all sentences over VV: : Denoted Denoted VV**..Grammars•A formal A formal grammargrammar GG is any compact, precise is any compact, precise mathematical definition of a language mathematical definition of a language LL..–As opposed to just a raw listing of all of the language’s As opposed to just a raw listing of all of the language’s legal sentences, or just examples of them.legal sentences, or just examples of them.•A grammar implies an algorithm that would A grammar implies an algorithm that would generate all legal sentences of the language.generate all legal sentences of the language.–Often, it takes the form of a set of recursive definitions.Often, it takes the form of a set of recursive definitions.•A popular way to specify a grammar recursively is A popular way to specify a grammar recursively is to specify it as a to specify it as a phrase-structure grammar.phrase-structure grammar.Phrase-Structure Grammars•A A phrase-structure grammarphrase-structure grammar (abbr. PSG) (abbr. PSG) GG = ( = (VV,,TT,,SS,,PP)) is a 4-tuple, in which: is a 4-tuple, in which:–VV is a vocabulary (set of words) is a vocabulary (set of words)•The “template vocabulary” of the language.The “template vocabulary” of the language.–TT  VV is a set of words called is a set of words called terminalsterminals •Actual words of