Đang chuẩn bị liên kết để tải về tài liệu:
Lecture Formal methods in software engineering: Finite automata

Lecture Formal methods in software engineering: Finite automata. In this chapter, the following content will be discussed: Yet another method for defining languages, fas and their languages, even-even revisited, how does a finite automaton work? Transition table, FA and their languages. | Finite Automata Lecture # 07 Qaisar Javaid Assistant Professor Finite Automata Yet Another Method for Defining Languages FAs and Their Languages EVEN-EVEN Revisited Yet Another Method for Defining Languages Definition A finite automaton is a collection of three things: A finite set of states, one of which is designated as the initial state, called the start state, and some (maybe none) of which are designated as final states. 2. An alphabet Σ of possible input letters. 3. A finite set of transitions that tell for each state and for each letter of the input alphabet which state to go next. How Does a Finite Automaton work? It works by being presented with an input string of letters that it reads letter by letter starting from the leftmost letter. Beginning at the start state, the letters determine a sequence of states. This sequence ends when the last input letter has been read We will use the term FA for the phrase “finite automaton”. Example Consider the following FA: The input alphabet has only the two letters a and b. (We usually use this alphabet throughout the chapter.) There are only three states, x, y and z, where x is the start state and z is the final state. The transition list for this FA is as follows: – Rule 1: From state x and input a, go to state y. – Rule 2: From state x and input b, go to state z. – Rule 3: From state y and input a, go to state x. – Rule 4: From state y and input b, go to state z. – Rule 5: From state z and any input, stay at state z. Example Contd. Let us examine what happens when the input string aaa is presented to this FA. First input a: state x → y by Rule 1. Second input a: state y → x by Rule 3. Third input a: state x → y by Rule 1. We did not finish up in the final state z, and therefore have an unsuccessful termination. Example contd. The set of all strings that lead to a final state is called the language defined by the finite automaton. Thus, the string aaa is not in the language defined by this . | Finite Automata Lecture # 07 Qaisar Javaid Assistant Professor Finite Automata Yet Another Method for Defining Languages FAs and Their Languages EVEN-EVEN Revisited Yet Another Method for Defining Languages Definition A finite automaton is a collection of three things: A finite set of states, one of which is designated as the initial state, called the start state, and some (maybe none) of which are designated as final states. 2. An alphabet Σ of possible input letters. 3. A finite set of transitions that tell for each state and for each letter of the input alphabet which state to go next. How Does a Finite Automaton work? It works by being presented with an input string of letters that it reads letter by letter starting from the leftmost letter. Beginning at the start state, the letters determine a sequence of states. This sequence ends when the last input letter has been read We will use the term FA for the phrase “finite automaton”. Example Consider the following FA: