Regular Language Finite Automata California Stat University 正則語(yǔ)言的有限自動(dòng)機(jī)加利福尼亞州立大學(xué)

1、cs490 presentation:automata & language theorythong lamran shicomponents of a formal languagensymbolnalphabetnstringngrammarcomponents of a formal languagea character, glyph, mark. an abstract entity that has no meaning by itself, often called uninterpreted. letters from various alphabets, digits

2、 and special characters are the most commonly used symbols. components of a formal languagea finite set of symbols. an alphabet is often denoted by sigma(components of a formal languagea finite sequence of symbols from an alphabet. 01110 and 111 are strings from the alphabet b above. aaabccc and b a

3、re strings from the alphabet c above. a null string is a string with no symbols, usually denoted by epsilon(components of a formal languagea way to define a language by giving a finite set of rules that describe how valid strings may be constructed.grammer(g) consists of an alphabet of terminals(for

4、mal language na set of strings from an alphabet.nthe set may be empty, finite or infinite. nl(m) is the notation for a language defined by a machine m. the machine m accepts a certain set of strings, thus a language. nl(g) is the notation for a language defined by a grammar g. the grammar g recogniz

5、es a certain set of strings, thus a language.n m(l) is the notation for a machine that accepts a language. the language l is a certain set of strings.ng(l) is the notation for a grammar that recognizes a language. the language l is a certain set of strings. formal languages (cont.)nthe union of two

6、languages is a language. l = l1 union l2 nthe intersection of two languages is a language. l = l1 intersect l2 nthe complement of a language is a language. l = sigma* - l1 nthe difference of two languages is a language. l = l1 - l2 regular languagena set of strings from an alphabet. nthe set may be

7、empty, finite or infinite. nmust be able to be represented as finite automataregular languagenuses:regular expressionsnmust be part of a regular languagenexample: 1+0*011 is a regular expression.finite automatan finite automata is also known as the finite state machinen it is a 5-tuple q, , , q0, fw

8、heren q is a finite set of states in the machinen is the input alphabetn is the transition from one state to the next staten q0 is the initial staten f is the set of all accepting states finite automata (cont.) for example: language consist of all strings have even number of 1s l=, 0, 0000, 11, 011,

9、 101, 110, 0011, 00011 evenodd1100finite automata (cont.)nfinite automaton, m:nm =q, , , q0, fnq=even, oddn=0,1n is described as 0 1 even even odd odd odd evennq0 =even nf=evenfinite automata (cont.)nthe type of finite automaton described in the preceding example is a deterministic finite automaton

10、(dfa).nan easer model to work with is the non-deterministic finite automaton (nfa)finite automata (cont.)nwhile in a dfa, every state must have exactly one transition path for each symbol in the automatons alphabet, an nfa can have as one, none, or as many transition path as it needs for each symbol

11、 in the alphabet. nan nfa can also have a transition path(s) for the empty input, .ndfa s and nfas are equivalentfinite automatanexample of nfa:abcdd0,101 0,1regular languages: finite automatanfinite automaton, n:nn=q, , , q0, fnq=a,b,c,dn=0,1n is described as: 0 1 a c b b c c d d d d d nq0 = anf=dc

12、ontext-free languagesna set of strings from an alphabet. nthe set may be empty, finite or infinite.nincludes a pumping lemma.npush down automata(pda).ncontext-free grammer(cfg).context-free languages:pushdown automatonnpushdown automaton is a 6-tuple q,s,u,p,i,f, where:nq is a finite set of statesns

13、 is input alphabetnu is stack alphabetnp is transition stateni is initial statenf is final statecontext-free languages:pushdown automatafor example, we have a string aabba input string (read in opposite to the string that we have)a b b a acuread input stringtransition occursstackcu can read or write

14、 to stackcontext-free language:pushdown automatanfor example : l = anbn | n0165423push bscan bscan apush ascan bpop apop bshow the configuration sequence on input aabbq: 1, 2, 3, 4, 5, 6 (1, , ) s: a, b (2, , b)u: b, a (3, a, b)i : 1 (2, a, ba)f: 6 (3, aa, ba)p: 1) push (b, 2) (2, aa, baa) 2) scan (

15、a, 3) (b, 4) (4, aab, baa) 3) write (a, 2) (5, aab, ba) 4) read (a ,5) (b, 6) (4, aabb, ba) 5) scan (b, 4) (5, aabb, b) 6) (6, aabb, )context-free language:context-free grammarsncontext-free grammar is a 4-tuple v, , r,s, where:nv is a finite set of variablesn is a finite set of terminals nr is a fi

16、nite set of rules, andns is the start variablecontext-free languages: context-free grammars example of cfg s turing machinesnturing machines (tm) are similar to pdas, but with memory that is unlimited and unrestricted.nthe turing machine uses an infinite tape.nthe tape head can read and write symbol

17、s on the tape. it can also move to the left or right over the tape.nturing machines have accept states and reject states, which take immediate effect.turing machinesbb x1x2xixnbbfinite controlturing machines the tm we construct will accept the language 0n1n | n1 1. it is given a finite sequence of 0

18、s and 1s on its tape, preceded and followed by an infinity of blanks. 2.the tm will change a 0 to an x and then a 1 to a y, until all 0s and 1s have been matched. 3. starting at the left end of the input, it repeatedly changes a 0 to an x and moves to the right over whatever 0s and ys it sees, until

19、 it comes to a 1. 4. it changes the 1 to a y, and moves left, over ys and 0s , until it finds an x. at that point, it looks for a 0 immediately to the right, and if it finds one, changes it to x and repeats the process, changing a matching 1 to a y. 5. if the nonblank input is not in 0*1*, then the

20、tm fail to have next move and will die without accepting. 6. if it finishes changing all the 0s to xs on the same round it changes the last 1 to a y, then it has found its input to be of the form 0n1n and accepts. the formal specification to the tm m is m= (q0 , q1 , q2 , q3 , q4 , 0,1, 0,1,x,y,b , , q0, bq4) where is state 0 1 x y b q0 (q1, x, r) - - (q3, y,r) - q1 (q1, 0