tailieunhanh - INTRODUCTION TO COMPUTER SCIENCE - PART 7

AUTOMATA Mô hình là một tập hợp các đối tượng với một số tài sản được công nhận. Một loại của mô hình là một thiết lập các chuỗi ký tự, chẳng hạn như các thiết lập của pháp luật nhận dạng C, mỗi trong số đó là một chuỗi chữ cái, chữ số, gạch dưới, bắt đầu với một lá thư hay gạch dưới. Với một mô hình và một đầu vào, quá trình xác định nếu đầu vào phù hợp với mô hình được gọi là mô hình kết hợp, một vấn đề còn được gọi là nhận dạng mẫu. trong biên dịch,. | INTRODUCTION TO COMPUTER SCIENCE HANDOUT 7. AUTOMATA K5 K6 Computer Science Department Văn Lang University Second semester -- Feb 2002 Instructor Trăn Đức Quang Major themes 1. Patterns and Pattern Matching 2. Finite State Machines and Automata 3. Deterministic and Nondeterministic Automata Reading Sections and . PATTERNS AND PATTERN MATCHING A pattern is a set of objects with some recognizable property. One type of pattern is a set of character strings such as the set of legal C identifiers each of which is a string of letters digits and underscores beginning with a letter or underscore. Given a pattern and an input the process of determining if the input matches the pattern is called pattern matching a problem also known as pattern recognition. In compiling for example one of the essential parts is to regconize construct patterns in programs before translating programs into a desired code. Let s see an illustration for the first phase of this process. Consider an if-statement in C if a b x 1 A C compiler will read input characters from the left one at a time collect them into small groups of characters lexemes or tokens matching some lexical pattern. This phase is called lexical analysis. Our statement for example may be grouped into the following tokens each has its own pattern 1. The keyword if 2. The left parenthesis 3. The identifier a 4. The comparison operator 40 INTRODUCTION TO COMPUTER SCIENCE HANDOUT 7. AUTOMATA 5. The identifier b 6. The right parenthesis 7. The identifier x 8. The assignment operator 9. The integer 1 10. The statement-terminator White space characters blanks tabs and newlines would also be eliminated. STATE MACHINES AND AUTOMATA Programs that search for patterns often have a special structure. We can identify certain positions in the code at which we know something particular about the program s progress toward its goal of finding an instance of a pattern. We call these positions states. The overall behavior of the .