1. Lecture # 22 Theory Of Automata By Dr. MM Alam 1
2. Lecture#21 at a glance… • JFLAP for Pumping Lemma Version II – Practical Demonstrations
3. Context Free Grammar • For earliest computers . Every procedure, no matter how complicated, had to be spelled out in the crudest set of instructions: • They accepted no instructions except those in their own machine language. • It could take dozens of these primitive instructions to do anything useful. 3
4. Context Free Grammar • For example to calculate • This clearly required that some "higher- level" language be invented-a language in which one mathematical step, such as evaluating the formula above, could be converted into one single computer 4
5. Context Free Grammar • A super program called the compiler does the conversion from a high-level language into assembler language code. • It cannot just look at the expression and understand it. • Rules must be given by which this string can be processed. 5
6. Context Free Grammar • Also we want our machine to be able to reject strings of symbols that make no sense as arithmetic expressions. Like "((9)+". • This input string should not take us to a final state in the machine. • However, we cannot know that this is a bad input string until we have reached the last letter. 6
7. Context Free Grammar • If the + were changed to a ), the formula would be valid. • An FA that translated expressions into instructions as it scanned left to right would already be turning out code before it realized that the whole expression is nonsense. 7
8. Context Free Grammar • Rules for valid arithmetic expressions. Rule 1 Any number is in the set AE. Rule 2 If x and y are in AE then so are: (x) -(x) (x + y) (x - y) (x*y) (x/y) (x**y) • For example, the input string • ((3 + 4) * (6 + 7)) 8
9. Context Free Grammar • The way this can be produced from the rules is by the sequence 3 is in AE 4 is in AE (3 + 4) is in AE 6 is in AE 7 is in AE (6 + 7) is in AE ((3 + 4) * (6 + 7)) is in AE 9
10. Context Free Grammar • Convert this into LOAD 3 in Register 1 LOAD 4 in Register 2 ADD the contents of Register 2 into Register 1 LOAD 6 in Register 3 LOAD 7 in Register 4 ADD the contents of Register 3 into Register 4 MULTIPLY Register 1 by Register 4 10
11. Context Free Grammar • It was realized by earlier high-level languages designers that this problem is analogous to the problem humans have to face hundreds of times every day when they must decipher the sentences that they hear or read in English. • "grammar" -- Study of grammar as well as the set of rules themselves, we sometimes refer to the set of rules as forming a "generative grammar.” 11
12. Context Free Grammar • According to the rules in English grammar that allows us to form a sentence by juxtaposing a noun and a verb. • We might produce: Birds sing. • However, using the same rule might also produce: Wednesday sings. 12
13. Context Free Grammar • Semantics : – Rules that involve the meaning of words. • Syntax – Rules that do not involve the meaning of words. • In English the meaning of words can be relevant but in arithmetic the meaning of numbers is easy to understand. 13
14. Context Free Grammar • In the high-level computer languages, one number is as good as another. If X= B + 9 is a valid formulation then so are X = B + 8 X = B + 473 X = B + 9999 • So long as the constants do not become so large that they are out of range, 14
15. Context Free Grammar • We do not try to divide by 0, to take the square root of a negative number, and to mix fixed-point numbers with floating- point numbers in bad ways In general, the rules of computer language grammar are all syntactic and not semantic. 15
16. Context Free Grammar • In reality a law of grammar is a suggestion for possible substitutions. • Started out with the initial symbol Sentence. • Then the rules for producing sentences listed in the generative grammar are applied. • In most cases one have some choice in selecting which rule she wanted to apply. 16
17. Context Free Grammar • Terminals : – The words that cannot be replaced by anything . • Nonterminal: – Words that must be replaced by other things we call nonterminals. • Through the production procedure we developed the sentence into as many nonterminals as it was going to become. 17
18. Context Free Grammar • For defining arithmetic expressions We follow the same model. • We can write the whole system of rules of formation as the list of possible substitutions Start → (AE) AE → (AE + AE) AE → (AE - AE) AE → (AE *AE) 18 AE → (AE AE)
19. Context Free Grammar • The word "Start" is used to begin the process, as the word "Sentence“ was sued in the example of English. • Aside from Start, the only other nonterminal is AE. • The terminals are the phrase "any number" and the symbols + - * /** ( ) 19
20. Context Free Grammar • We are satisfied by knowing what is meant by the words "any number“. • OR else we could define this phrase by a set of rules, thus converting it from a terminal into a nonterminal. Rule 1: ANY-NUMBER ---> FIRST-DIGIT Rule 2: FIRST-DIGIT ---> FIRST-DIGIT OTHER- DIGIT Rule 3: FIRST-DIGIT--* 123456789 Rule 4: OTHER-DIGIT-->0 123456789 20