Lecture Theory of Automata: Lesson 37. The main topics covered in this chapter include: new format for FAs, input TAPE, START, ACCEPT, REJECT, READ states examples of new format of FA, PUSH down STACK, PUSH and POP, example of PDA, when a letter is pushed, it replaces the existing letter and pushes it one position below, . | ReCap Chomsky Normal Form Theorem regarding CNF examples of converting CFG to be in CNF Example of an FA corresponding to Regular CFG Left most and Right most Solution of the Task Convert the following CFG to CNF S ABAB A a B b Solution Removing the null productions A and B and introducing the new productions as S BAB AAB ABB ABA AA AB BA BB A B Solution contd Removing the unit productions S A B and introducing the new productions as S a b Introducing the new nonterminal R to convert the productions of the form S string of four nonterminals to the form S string of two nonterminals as R AB Solution continued Thus the required CNF becomes S RR AR BR RA RB AA AB BA BB a b R AB A a B b A new format for FAs A class of machines FAs has been discussed accepting the regular language . corresponding to a regular language there is a machine in this class accepting that language and corresponding to a machine of this class there is a regular language accepted by this machine. It has also been discussed that there is a CFG corresponding to regular language and CFGs also define some nonregular languages as well A new format for FAs contd. There is a question whether there is a class of machines accepting the CFLs The answer is yes. The new machines which are to be defined are more powerful and can be constructed with the help of FAs with new format. To define the new format of an FA the following are to be defined A new format for FAs contd. Input TAPE The part of an FA where the input string is placed before it is run is called the input TAPE. The input TAPE is supposed to accommodate all possible strings. The input TAPE is partitioned with cells so that each letter of the input string can be placed in each cell. The input string abbaa is shown in the following input TAPE. Input TAPE contd Cell i Cell ii Cell iii a b b a a . The character indicates a blank in the TAPE. The input string is read from the TAPE starting from the cell i . It is assumed that when first is read .
