tailieunhanh - Lecture Theory of automata - Lecture 37

This chapter presents the following content: New format for FAs, input TAPE, START, ACCEPT , REJECT, READ states Examples of New Format of FAs, PUSHDOWN STACK , PUSH and POP states, Example of PDA. | 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 . | 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 The character ∆ indicates a blank in the TAPE. The input string is read from the TAPE starting from the cell (i). It is assumed