III. Supplementary MaterialsSupplementary Materials The Three Hour Tour Through Automata Theory 1 The Three Hour Tour Through Automata Theory Analyzing Problems as Opposed to Algorithms In CS336 you learned to analyze algorithms. This semester, we're going to analyze problems. We're going to see that there is a hierarchy of problems: easy, hard, impossible. For each of the first two, we'll see that for any problem, there are infinitely many programs to solve the problem. By the way, this is trivial. Take one program and add any number of junk steps. We'll formalize this later once we have some formalisms to work with. Some may be better than others. But in some cases, we can show some sort of boundary on how good an algorithm we can attempt to find for a particular problem. Let's Look at Some Problems Let's look at a collection of problems, all which could arise in considering one piece of C++ code. [slide - Let's Look at Some Problems] As we move from problem 1 to problem 5, things get harder in two key ways. The first is that it seems we'll need more complicated, harder to write and design programs. In other words, it's going to take more time to write the programs. The second is that the programs are going to take a lot longer to run. As we get to problems 4 and 5, it's not even clear there is a program that will do the job. In fact, in general for problem 4 there isn't. For problem 5, in general we can't even get a formal statement of the problem, much less an algorithmic solution. Languages Characterizing Problems as Language Recognition Tasks In order to create a formal theory of problems (as opposed to algorithms), we need a single, relatively straightforward framework that we can use to describe any kind of possibly computable function. The one we'll use is language recognition. What is a Language? A language is a set of strings over an alphabet, which can be any finite collection of symbols. [Slide - Languages] Defining a Problem as a Language Recognition Task We can define any problem as a language recognition task. In other words, we can output just a boolean, True or False. Some problems seem naturally to be described as recognition tasks. ForSupplementary Materials The Three Hour Tour Through Automata Theory 2 example, accept grammatical English sentences and reject bad ones. (Although the truth is that English is so squishy it's nearly impossible to formalize this. So let's pick another example -- accept the syntactically valid C programs and reject the others.) Problems that you think of more naturally as functions can also be described this way. We define the set of input strings to consist of strings that are formed by concatenating an input to an output. Then we only accept strings that have the correct output concatenated to each input. [Slide - Encoding Output] Branching Out -- Allowing for Actual Output Although it is simpler to characterize problems simply as recognition problems and it is possible to reformulate functional problems as recognition problems, we will see that we can augment the formalisms we'll develop to allow for output as well. Defining Languages Using Grammars Now what we need is a general mechanism for defining languages. Of course, if we have a finite language, we can just enumerate all the strings in it. But most interesting languages are infinite. What we need is a finite mechanism for specifying infinite languages. Grammars can do this. The standard way to write a grammar is as a production system, composed of rules with a left hand side and a right hand side. Each side contains a sequence of symbols. Some of these symbols are terminal symbols, i.e., symbols in the language we're defining. Others are drawn from a finite set of nonterminal symbols, which are internal symbols that we use just to help us define the language. Of these nonterminal symbols, one is special -- we'll call it the start symbol. [Slide - Grammars 1] If there is a grammar that defines a language, then there is an infinite number of such grammars. Some may be better, from various points of view than others. Consider the grammar for odd integers. What different grammars could we write? One thing we could do would be to introduce the idea of odd and even digits. [Slide - Grammars 2] Sometimes we use single characters, disjoint from the characters of the target language, in our rules. But sometimes we need more symbols. Then we often use < and > to mark multiple character nonterminal symbols. [Slide - Grammars 3] Notice that we've also introduced a notation for OR so that we don't have to write as many separate rules. By the way, there are lots of ways of writing a grammar of arithmetic expressions. This one is simple but it's not very good. It doesn't help us at all to determine the precedence of operators. Later we'll see other grammars that do that. Grammars as Generators and as Acceptors So far, we've defined problems as language recognition tasks. But when you look at the grammars we've considered, you see that there's a sense in which they seem more naturally to be generators than recognizers. If you start with S, you can generate all the strings in the languageSupplementary Materials The Three Hour Tour Through Automata Theory 3 defined by the grammar. We'll see later that we'll use the idea of a grammar as a generator (or an enumerator) as one way to define some interesting classes of languages. But you can also use grammars as acceptors, as we've suggested. There are two ways to do that. One is top-down. By that we mean that you start with S, and apply rules. [work this out for a simple expression for the Language of Simple Arithmetic Expressions] At some point, you'll generate a string without any nonterminals (i.e., a string in the language). Check and see if it's the one you want. If so accept. If not, try again. If you do this systematically, then if the string is in the language, you'll eventually generate it. If it isn't, you may or may not know when you should give up. More on that later. The other approach is bottom up. In this approach, we simply apply the rules sort of backwards, i.e., we run them from right to left, matching the string to the right hand sides of the rules and continuing until we generate S and nothing else. [work this out for a simple expression for the Language of Simple Arithmetic
View Full Document
Unlocking...