Formal Languages, Automata, Computation
Formal Languages, Automata,Computation1AdministriviaKlaus Sutner Carnegie Mellon UniversityFLACFall 2019Web & Piazza3Piazza4. . . is greatIt’s a good way to share information and get answers withoutterrible delays.http://www.cs.cmu.edu/ flac. . . suckshttp://piazza.com/ It can be used to avoid work by asking lots of silly questions, andrelying on others to do all the heavy lifting.15-453This is an upper lever class, don’t play games.Also, don’t repost the same question a dozen times.Course StaffProf:Klaus Sutner, sutner@cs.cmu.edu,http://www.cs.cmu.edu/ sutner5Course MaterialNo textbook, but lots of material on the web.If you absolutely want to have a textbook:TAs:Paul Gölz, pgoelz@andrew.cmu.eduCourse secretary:Rosie Battenfelder, rosemary@cs.cmu.eduM. SipserIntroduction to the Theory of ComputationCengage India, 20146
Sipser7Learning StyleThe book is based on a great idea: for a complicated proof, first presenta fairly informal sketch, outlining the main ideas.The topics covered in this course translate into quite a bit ofmaterial. Allocate enough time to deal with this material.Then get down into the weeds and produce a formal argument.Read the notes, search the net, go to the library, talk to each other,talk to us.Again, great idea, but in reality the difference between the informal andthe formal argument is a bit anemic. You really get a sketch, and then adetailed sketch. I know this is an obnoxious thing to say at this point,but in the back of your mind always think about a theorem prover.Post on piazza (but make sure to read previous posts first).Samuel Beckett8One of the desired outcomes of this course is that you know whereto find more information should you ever need it (the lifelonglearning meme).9Bureaucracy10The usual testing:Ever tried. Ever failed. homeworks 50% midterm (in-house) 20% final 30%No matter. Try Again. Fail again. Fail better.There are no makeups; if you miss some assessment you can sit foran oral exam.Worstward Ho!Bureaucracy IIMidterm is in-house, 80 minutes on Oct 19.Final will be a project (think 8 pages), more later.Homework is obviously critically important.It’s 50% of your grade, so I trust you to do the work yourself.I hate having to play policeman.11Preserving TA SanityTypeset your solutions to the homework and submit pdf on afs(more on this on Piazza).If you have extensive conversations with other students about a HW,mention them as “collaborators” in your submission.If you use a computer program in your homework, make sure toreference it properly (but do not hand in 50 pages of code).12
Lateness13CooperationYou have a total of 6 (six) late days at your disposal; use prudently.14Lectures will be warm and friendly. Make sure to be an activeparticipant – FLAC is not a spectator sport.A late day is a discrete atom, with no smaller parts.Mention lateness in the header of your HW.You are strongly encouraged to talk about the course material toeach other, the course staff and other students.I reserve the right to give you no credit at all for work submittedbeyond the allotted time.This includes discussions of homework problems.Limits to Cooperation15More on LimitsThink of this as being able to copyright your solution: you may havehad conversations about it with other during the problem solvingphase, but the actual work is solely yours. No one should be in theroom when you start writing things up.However, even after ample consultation, the work you submit mustbe written entirely by yourself.List all your “consultants” on the first page of your homework. Wewill provide a convenient template.Needless to say, you have to be able to explain all the details of yoursolution at any time.To avoid problems with originality, do not take notes whendiscussing homework problems.Don’t even think about copy & paste (from each other or the web),file sharing, clairvoyance, telepathy, . . .If you write on a board, erase everything in the end.Yet More on LimitsAnd, of course, all the official university policies apply.16If you have any questions about policy issues talk to the course staff,preferably some time before you get into trouble.17Email18Some of you may still remember email (a medieval communication tool,predating social networks). If you decide to get in touch via email, useSubject line:[FLAC] will miss .htmlor some such. I filter rather aggressively, make sure to have the [FLAC]tag.
Wellness19Take care of yourself. Do your best to maintain a healthy lifestyle thissemester by eating well, exercising, avoiding drugs and alcohol, gettingenough sleep and taking some time to relax. This will help you achieveyour goals and cope with stress.Wellness II20If you or someone you know is feeling suicidal or in danger of self-harm,call someone immediately, day or night:All of us benefit from support during times of struggle. There are manyhelpful resources available on campus and an important part of thecollege experience is learning how to ask for help. Asking for supportsooner rather than later is almost always helpful.CaPS: 412-268-2922Re:solve Crisis Network: 888-796-8226If the situation is life threatening, call the policeOn campus: CMU Police: 412-268-2323Off campus: 911If you or anyone you know experiences any academic stress, difficult lifeevents, or feelings like anxiety or depression, we strongly encourage youto seek support. Counseling and Psychological Services (CaPS) is here tohelp: call 412-268-2922 and visit their website athttp://www.cmu.edu/counseling/. Consider reaching out to a friend,faculty or family member you trust for help getting connected to thesupport that can help.Formal Languages, Automata, Computation22This is the official course title for 15-453. AdministriviaMostly a historical artifact, a better title would beCAFL: Computation, Automata, Formal Languages2FLACWe’ll start with the general theory of computation, then dive all the waydown to finite state machines, and then talk a bit about the Chomskyhierarchy and complexity theory.The Computational UniverseThis may sound like just a whole bunch of math.It is, but this is a CS course: we don’t live in the set-theory universe ofmath, we live in the computational universe.23Theory FirstA (ironic?) fact of history:The theory of computation predates computers.What matters to us is not just the pure mathematical theory, but itscomputational meaning. In particular we want to emphasize algorithms.In fact, computability theory was closely connected to problems in thefoundations of mathematics in the 1930s, there simply was no computerscience at the time. Bear this in mind, otherwise things may occasionallyseem a bit bizarre.As you will see, this makes life much more interesting, but also quitechallenging: we need our arguments to be constructive andcomputational, not just logically correct.As it turns out, computability theory is highly relevant to computerscience, but one needs a bit of background to see why.24
Early History25Eratosthenes26Around 240 BCE, error may have been as low as 1%. Also calculateddiameter of sun, not as accurate (27 times Earth, in reality 109).Early mathematics was very much focused on computation (Plimpton322, about 1800 BCE).Beginnings of Abstraction27Full Abstraction28Things changed when the field matured. For example, the mainaccomplishments in mathematics in the 19th century can be summarizedlike so:complex variablesabstract groupsset theoryWhile such “top ten” lists are often contentious, this one is fairlyuncontroversial.Note that computation is essentially absent, the level of abstraction israther high (logical depth).Even More Abstraction29What Could Go Wrong?30Despite all the progress, in the last third of the 19th century a number ofannoying problems came to light.If Gauss says he has proved something, it seems very probableto me; if Cauchy says so, it is about as likely as not; if Dirichletsays so, it is certain.Carl Gustav Jacob JacobiFor example, seemingly intuitive notions in analysis such as continuityand differentiability are much more subtle than they might seem. It isvery, very easy to trip up.
Levels of Trouble31Weierstrass Monster32f (x) Xbn cos(an πx)n 0paradox para doxa; outside of the doctrine, a misalignment withcommon sense21.5antinomy anti nomos; against the law, not just a misalignment, butsomething offensive, in need of correction10.5contradiction contra dicere; to speak against, a direct counterargument,all hell breaks loose (aka inconsistency)0.511.522.53-0.5-1-1.5This hierarchy is non-standard and entirely informal, don’t over-interpret.For 0 b 1 and ab 1 3/2π, this function is continuous butnowhere differentiable. A mild paradox.Cantor’s Work33More Trouble in Paradise34Burali-FortiThe unit square has the same size as the unit interval.The set of all ordinal numbers.There are more reals than rationals.RussellThere is an infinite hierarchy of increasing infinities.S {x x / x}König, RichardThe least natural number not definable by at most 100 words.Paradoxical, no more.Remarkably, Cantor was lead to his discoveries by studying Fourieranalysis, a relentlessly applied part of mathematics.ChurchSome actual antinomies, but perhaps not quite at the level where thewhole system needs to come crashing down.35Church’s first attempt at the λ-calculus allows for a termk λx.( (xx))But then we have the “Kleene-Rosser paradox”kk (kk)This seems to be fatal, and requires a complete restart (typedλ-calculus).It is easier than you may think to construct an inconsistent system.Bad ProofsThe Four Color Theorem was first conjectured in 1852 by F. Guthrie: anymap planar can be colored with just four colors.A. Kempe published a “proof” in 1879, but an error was found by P.Heawood in 1890. Heawood gave a correct proof of the weaker FiveColor Theorem.An alternative “proof” was given in 1880 by P. G. Tait, but his argumenttoo had a bug, discovered in 1891 by J. Petersen.The first major step forward came in 1969 when H. Heesch managed toshow that the proof could be reduced to checking finitely many cases.This opened the door for a computer-assisted proof: Appel and Haken1976, Gonthier 2006.36
Grundlagenkrise37Hilbert and Poincaré3839Hilbert’s Program40Adding up all these little insults and injuries to mathematical thoughtultimately added up to a major crisis: it was no longer clear thatmathematics was the ultimate standard for reliability and precision, thequeen of the sciences that dwarfed all other efforts.To be sure, most mathematicians blithely ignored these issues, they weremore than happy to apply a highly developed machinery that couldapparently dismember problems of any complexity. Math worked, andwho cares about philosophical objections?Blowback. . . dispose of the foundational questions in mathematics assuch once and for all.Formalize mathematics and concoct a finite set of axiomsthat are strong enough to prove all theorems of mathematics(completeness) and show that the system is consistent; bystrictly finitary means. Also show that statements about“ideal objects” can be proven in the system, without usingideal objects.D. Hilbert, 1929Formerly, when one invented a new function, it was to further some practical purpose; today one invents them in orderto make incorrect the reasoning of our fathers, and nothingmore will ever be accomplished by these inventions.H. PoincaréPoincaré and Hilbert were arguably the two top mathematicians around1900; it is remarkable that their attitude towards foundational issues wasso diametrically opposed.Hilbert’s EntscheidungsproblemThe Entscheidungsproblem is solved when one knows a procedure by which one can decide in a finite number of operations whether a given logical expression is generally validor is satisfiable. The solution of the Entscheidungsproblemis of fundamental importance for the theory of all fields, thetheorems of which are at all capable of logical developmentfrom finitely many axioms.D. Hilbert, W. AckermannGrundzüge der theoretischen Logik, 1928In modern terminology: Hilbert wanted a decision algorithm, more or lessfor all of mathematics.41Rebuilding FoundationsIn a nutshell, Hilbert’s project seems to require at least the followingingredients:Formalization of mathematics. This requires in particular a formallogical system: a formal language, rules of inference, notion of proof,axiom systems that describe our domains of discourse.A completeness proof that shows that the system can prove all trueassertions.A consistency proof that shows that the system cannot prove acontradiction (soundness of the system).A decision algorithm that determines whether assertions in thesystem are true or false.42
The Trouble with Formal Systems43Gottlob Frege (1848-1925)4445Frege in Attack Mode46They don’t fit very well with the way actual humans conjecture, argue,think and reason.Every little detail of an argument has to be spelled out withmind-numbing precision. As a result, proofs get to be very, very long,and are more or less incomprehensible (to humans, at least).As a consequence, most mathematicians happily ignore logic and formalsystems. But note that writing a computer program is not much differentfrom writing a formal proof: the same, utterly annoying level of precisionand detail is required.Frege’s BooksHe criticizes others (Dedekind, Peano) for the lack of precision in theirwork.Begriffsschrift 1879 Introduces a surprisingly modern and careful systemof logic (except for notation). The first real step forwardsince Leibniz.It cannot be demanded that everything be proved, becausethat is impossible; but we can require that all propositionsused without proof be expressly declared as such, so thatwe can see distinctly what the whole structure rests upon.After that we must try to diminish the number of primitivelaws as far as possible, by proving everything that can beproved. Furthermore, I demand–and in this I go beyondEuclid–that all methods of inference employed be specifiedin advance.Grundlagen 1884 Critique of previous foundational efforts, outline of hisown project.Grundgesetze 1893/1903 Develops theory of arithmetic and analysis inhis system. Ruined by Russel’s discovery.This is from “Grundgesetze der Arithmetik I,” published in 1893.Alas . . .47The next large-scale attempt to provide a formal foundation for a largefragment of mathematics was undertaken by by Russell and Whitehead,leading to publication of three volumes 1910–1913.Q(y)P (x, y)Q(x)baaPrincipia MathematicaQ(a)P (b, a)Q(b)Q(y)P (x, y)Q(a)P (x, a)PM was a remarkable effort and absolutely groundbreaking. Alas, boththeir notation system and their ontological assumptions were notsustainable. Russell later complained that his intellect“. . . never quite recovered from the strain of writing it.”From Frege’s 1879 “Begriffsschrift” (concept script).48
Principia Mathematica49Progress Surrounding Hilbert’s Program501889 Peano gives an axiomatization of basic number theory.1899 Hilbert gives an axiomatization of basic geometry.1910s Russell and Whitehead build a fairly comprehensive formalsystem of mathematics based on types.1918 Bernays shows that propositional logics is sound andcomplete.1929 Gödel shows that first-order logic is sound and complete.A Catastrophe51The operations on numbers representing formulae are all easilycomputable.There is a formula of number theory such that Peano arithmetic proves neither the formula nor its negation.Since they are easily computable, they can be handled by any formalsystem that is is expressive enough to cover some basic aspects ofarithmetic.Since either the formula or its negation must be true, we are missing outon a true statement of arithmetic.It seems that the only person in the audience who understood what wasgoing on was von Neumann. Hilbert was in Königsberg, he gave his“werden wissen” speech the next day, but apparently he did not attendGödel’s lecture.Note the irony: computability helps to demolish Hilbert’s dream, whichbasically says everything is computable.53“The standard of correctness and completeness necessary toget a computer program to work at all is a couple of ordersof magnitude higher than the mathematical community’sstandard of valid proofs.”W. ThurstonNotices AMS 199452One key idea in Gödel’s proof is arithmetization: one can expressformulae and proofs, plus all necessary manipulations, in terms ofarithmetic. (The other is the Liar’s Paradox.)The Incompleteness Theorem was announced by Gödel on October 7,1930, at a conference in Königsberg, the “First International Conferenceon the Philosophy of Mathematics”:Computer ScienceComputationSequencing54We will follow the historical chain of events:1930s Computability theory1950s Automata theory1970s Complexity theoryTo a programmer, all this may sound oddly familiar: mind-numbingprecision is also required in writing programs. In fact, much of thecomputability/complexity/automata machinery that is relevant for theGrundlagenkrise is also directly relevant to CS.Why? There are good reasons things happened in this particular order.
ComputabilityThere are several problems we need to tackle:Give a precise and robust definition of computability.Provide evidence that our definition adequately reflects the intuitivenotion of computability.Study the basic properties of computability and prove the mainresults in the area.Develop tools to show that some problems are computationallysolvable or fail to be so solvable.Do the same for a theory of tractable problems and practicalcomputation.55Turing’s Machines56
Formal Languages, Automata, Computation 22 This is the o cial course title for 15-453. Mostly a historical artifact, a better title would be CAFL: Computation, Automata, Formal Languages We'll start with the general theory of computation, then dive all the way down to nite stat
Advanced Automata Theory is a lecture which will rst review the basics of formal languages and automata theory and then give insight into speci c topics from wider area of automata theory. In computer science, automata are an important tool for many theoretical results and various types of automata
Automata and Formal Languages II Tree Automata Peter Lammich SS 2015 1/161. Overview by Lecture Apr 14: Slide 3 Apr 21: Slide 2 Apr 28: Slide 4 May 5: Slide 50 . Finite tree automata: Basic theory (TATA Ch. 1) Pumping Lemma, Clo
Introduction to the Theory of Computation Formal Languages and Automata Models of Computation Jean Gallier May 27, 2010. 2. Chapter 1 Basics of Formal Language Theory . We will investigate automata of increasing power of recog-nition: (1) Deterministic and nondeterministic finite automata
CIT 342 Formal Languages and Automata Theory Introduction CIT 342 – Formal Languages and Automata Theory is a two (2) credit unit course of 16 units. The course will cover the important formal languages in the Chomsky hierarchy -- the regu
Automata Theory, Languages, and Computation S ECO IN O EDITION Pearson Educatic ULBI Hil Darmstadtl III 16356298 River, N.J. 07458. Table of Contents . 1.1.1 Introduction to Finite Automata 2 1.1.2 Structural Representations 4 1.1.3 Automata and Complexity 5 1.2 Introduction to Formal Proof 5 1.2.1 Deductive Proofs 6 1.2.2 Reduction to .
(Recognizable languages) Are certain automata . closed . under union, intersection, or complementation of formal languages? (Closure properties) How much is a type of automata expressive in terms of recognizing class of formal languages? And, their relative expressive power? (Language Hie
Automata Theory, Languages, and Computation 3 . INTRODUCTION TO Automata Theory, Languages, and Computation JOHN E. HOPCROFT Cornell University RAJEEV MOTWANI Stanford University JEFFREY D. ULLMAN Stanford University 3 rd Edition hopcroft_titlepgs 5/8/06 12:43 PM Page 2. Publisher Greg Tobin
Financial accounting provides the rules and structure for the conveyance of financial information about businesses (and other organizations). At any point in time, some businesses are poised to prosper while others teeter on the verge of failure. Many people are seriously interested in evaluating the degree of success achieved by a particular organization as well as its . Saylor URL: http .
