CS423 Finite Automata & Theory Of Computation

2y ago
76 Views
2 Downloads
422.38 KB
190 Pages
Last View : 16d ago
Last Download : 2m ago
Upload by : Francisco Tran
Transcription

CS423 Finite Automata & Theory ofComputationTTh 2:00 - 3:20 on Zoom or anytime on BlackboardProf. Weizhen Mao, wm@cs.wm.edu or wxmaox@wm.edu,Zoom meeting ID 7572213472, Zoom passcode 2718281

General InformationI Office Hours: On Zoom. Time to be determinedI Grader: TBDI Textbook: Intro to the theory of computation (any edition),Michael Sipser.I Prerequisites/background: Linear algebra, Data structuresand algorithms, and Discrete math2

Use of BlackboardI AnnouncementsI HomeworkI Solution setsI Lecture notesI Recorded lecturesI Grades (HWs, Midterm, Final)I Check at least weekly3

Lecture Notes (in various forms and places)I Lecture slides: http://www.cs.wm.edu/ wm/I Lecture notes posted on BB (A high-level summary)I Recorded lecture posted on BBI Your own class notesCourse OrganizationI Automata theory: 50%I Computability theory: 25%I Complexity theory: 25%4

GradingI 10 homework assignments: 35%I Midterm: 25%I Final: 40%Grading PolicyI [90, 100]: A or AI [80, 90): B , B, or BI [70, 80): C , C, or CI [60, 70): D , D, or DI [0, 60): F5

Homework Submission PolicyI Your homework needs to be typeset in LaTex with allfigures drawn nicely and inserted. The pdf file needs to besubmitted to BB before or on the due dateI Extensions may be permitted for illness and familyemergency. Requests must be made prior to the due date6

Homework Completion PolicyI Homework must be typeset in LaTex. Nothing should behandwritten, including diagrams and tablesI Empty-hand policy when you discuss homework problemswith your classmatesI List your collaborators for every homework problemI Cite all references you used to solve a problemI In no case you should copy verbatim from other people’swork without proper attribution, as this is consideredplagiarism, thus a violation of the Honor Code7

ExamsI Midterm: Timed, on BB, and likely in mid-MarchI Final Exam: 2:00-5:00, May17 (Monday)8

Other Important DatesI Jan. 27: First day of classI Feb. 5: Last day to add/dropI Feb. 12: Spring break dayI Mar. 4: Spring break dayI Mar. 17: Spring break dayI Mar. 29: Last day to withdrawalI Apr. 6, 7: Spring break daysI Apr. 26: Spring break dayI May 7: Last day of class9

Writing Assignments for CSci423WI A paper of 3-4 pages about a someone pioneering the fieldof ToC and one of his/her major research contributions,written in the IEEE standard format for CS conferences.The title of the paper should be in the format of “name andresult”, e.g., “Alan Turing and the Enigma”, or “StephenCook and the Satisfiability Problem”, or “Rivest, Shamir,and Adleman and the RSA Cryptosystem”. More detailslater.I The class will be divided into ten groups, each beingresponsible for the production of one homework solutionset. More details later.10

Honor CodeI ”As a member of the William and Mary community, I pledgeon my honor not to lie, or steal, either in my academic orpersonal life. I understand that such acts violates theHonor Code and undermine the community of trust, ofwhich we are all stewards.”I Academic honesty, the cornerstone of teaching andlearning, lays the foundation for lifelong integrity. TheHonor Code is, as always, in effect in this course. Pleasego to the ”Honor System” page in the wm.edu site to readthe complete honor code document.11

Student Accessibility ServicesWilliam & Mary accommodates students with disabilities inaccordance with federal laws and university policy. Any studentwho feels they may need an accommodation based on theimpact of a learning, psychiatric, physical, or chronic healthdiagnosis should contact Student Accessibility Services staff at757-221-2512 or at sas@wm.edu to determine ifaccommodations are warranted and to obtain an official letter ofaccommodation. For more information, please go towww.wm.edu/sasPlease inform me privately of any accommodations you havearranged with the Office of SAS.My goal: I will try my best to be understanding, flexible, fair,and helpful, while creating a high quality learning experience forall of you.12

1.1 Three areas of ToC (Sipser 0.1)Theory of Computation is to study the fundamental capabilitiesand limitations of computers. It contains three areas.I Automata theory: Models of computation. Seeking aprecise but concise definition of a computer.I Computability theory: What can and cannot a computerdo? Computationally unsolvable versus computationallysolvable problems. Determining whether a problem isunsolvable by computer algorithms.I Complexity theory: What can a computer do efficiently?Computationally hard versus computationally easyproblems. For example, factorization versus sorting.Cryptography needs hard problems such as factorization toensure security.13

1.2 Sets and Languages (Sipser 0.2)Languages are central concepts in automata theory.I Alphabet Σ: Finite and nonempty, e.g., Σ {0, 1} andΣ {a, b, . . . , z}.I String (or word), e.g., w 01110: The empty string ε;length of a string, w ; concatenation of two strings w1 w2 ;reverse of a string w R , and substring of a string.I Language: A language is a set of strings, e.g., {ε}, 0,/ Σ,A {w w has an equal number of 0s and 1s} {ε, 01, 10, 0011, 0110, 1010, · · · }, andB {0n 1n n 1} {01, 0011, 000111, · · · }. Note B A.14

I Regular operators: Let A and B be two languages.I Union: A B {x x A or x B}.I Concatenation: A · B {xy x A and y B}.Example: If A {01, 10} and B {0, 1}, thenAB {010, 011, 100, 101}.I Star:A {x1 x2 · · · xk all k 0 and each xi A for i 1, 2, . . . , k }.Note ε A Example: If A {0, 1}, thenA {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 111, . . .}Example: If A {01, 11}, thenA {ε, 01, 11, 01 01, 11 01, . . . , 11 11 01 11, . . .}15

I More operatorsI Intersection: A B {x x A and x B}I Complement: A is the set of all elements underconsideration that are not in A. Usually, A Σ A.I Difference: A B A B.I Power: Ak {x1 x2 · · · xk xi A for i 1, 2, · · · , k }. NoteA0 {ε} and A A0 A1 A2 · · · .Example: If A {1, 01}, then A2 {11, 101, 011, 0101}Example: If A {01, 11, 0}, then A3 ? ( A3 27)Observation: If A n, then Ak A k nk .16

I Why languages, not problems:I Meta Claim: Computational problem decision problem.Example: Traveling Saleman problem (TSP)Input: G (V , E, w)Goal: Find a tour (cycle) with minimun total weightI Example: Decision problem for TSPInput: G (V , E, w) and B 0Question: Is there a tour in G such that the total weight ofthe tour is no more than B?I Decision problem: Given an input x, does x satisfy propertyP, or is x {y y satisfies P}?Input data of any form, such as matrix, graph, list, etc., canbe coded into stringsI Membership in a language: Given a language A and astring w Σ , is w a member of A, or is w A?17

1.3 Proof techniques (Sipser 0.4)I By definition: Convert terms in the hypothesis to theirdefinitions.I By construction: To prove the existence of X , construct it.I By contradiction: H C is equivalent to C H orC H T , where T is an axiom, a proven truth/fact.Example: The number of primes is infinite.Example: 2 is irrational.I By induction: Used to prove a statement S(n), n c.The logic behind the method:S(n) for n c iff S(c) k(S(k) S(k 1)).The proof includes (1) basis step, (2) inductive hypothesis,and (3) inductive step.Example: For n 1, ni 1 i 2 16 n(n 1)(2n 1).18

A Quick Review of LanguagesI Alphabet Σ, string or word, substring, languageI Common operations borrowed from set theory: union,intersection, differenceI New operations: concatenation, complement, star, power19

2.1 What is a Finite Automaton?(Sipser 1.1, 31-34)I Finite automata are the simplest computational models forcomputers with an extremely limited amount of memory.I Use of automata theory in software applications includes:study of the behavior of digital circuits, lexical analyzer incompilers, text pattern matching, and verification offinite-state systems.I They are designed to accept some strings, therefore torecognize a language, which is the set of accepted strings.I Given an input string, a finite automaton reads the string,one symbol at a time, from left to right. Using a transitionfunction, the FA changes from one state to another basedon what symbol is being read. Eventually, it reads allsymbols in the string. If at this time the FA enters a finalstate, then the FA halts and the string is accepted.20

Example 1 of a DFAI Alphabet: Σ {0, 1}.I Four states: q0 , q1 , q2 , q3 , in which q0 is the start state andq3 is a final state.01δ q0 q0 q1I Transition function δ:q1 q0 q2q2 q0 q3 q3 q3 q3I What does δ tell us?δ(q0 , 0) q0 , δ(q0 , 1) q1δ(q1 , 0) q0 , δ(q1 , 1) q2δ(q2 , 0) q0 , δ(q2 , 1) q3δ(q3 , 0) q3 , δ(q3 , 1) q321

Example 1 (continued)1011123000,10Figure 1: A DFA that accepts strings with substring 111Try w1 100111010 and w2 0011010001The language recognized/accepted isL1 {w {0, 1} w contains substring 111}22

2.2 DFA (Sipser 1.1, 35-44)I DFA M (Q, Σ, δ, q0 , F ), whereIIIIIQ is a finite set of statesΣ is an alphabetq0 Q is the start stateF Q is a set of accept/final statesδ : Q Σ Q is a transition function, where δ(q, a) p isthe next state of M if the current state is q and the currentsymbol is aI Components of a DFAI A tape of squares, with the same length of the input stringI A control unit that keeps track of the current state andfollows the δ functionI The head that reads and moves to the right, one square ata timeI The DFA accepts the input string if the head reaches theend of the tape and the control unit sees the final state23

I Extending δ to ˆδ : Q Σ Q: For any q Q and anyw xa Σ , define ˆδ(q, x) recursively as below:I ˆδ(q, ε) q andI ˆδ(q, w) δ(ˆδ(q, x), a)I Language recognized by DFA M: L(M) {w ˆδ(q0 , w) F }.I A language is called a regular language if some DFArecognizes it.I How does a DFA accept a string? A path in the diagramthat starts from q0 and ends at qf F such that theconcatenation of the symbols on the path matches theinput string.24

Example 2Let L2 {w {0, 1} w has even numbers of 0s and 1s}Construct DFA M such that L(M) L2 .0eeoe011110ooeo0Figure 2: A DFA that accepts strings of even number of 0s and 1s25

Example 3 (Sipser p. 36):A DFA M is given below:δ q0 q1q20q0q2q11q1q1q110011020, 1Figure 3: Describe the language of the DFA26

Example 3 (continued)The DFA in this example accepts strings that have at least one1 and an even number of 0s after the last 1.Reminder: More on DFA design in Sisper pp. 37-44.27

Example 4 Design a DFA that acceptsL4 {w {0, 1} w contains substring 001}001012300,111Figure 4: A DFA that accepts strings with substring 00128

Example 5 Give a DFA that acceptsL5 {w {0, 1} numerical value of w is a multiple of 3}, e.g.,for string 0110, its numerical value is 6, then it is in thelanguage, but for 101 with a numerical value of 5, it is not amultiple of 3, thus is not in the language.010112010Figure 5: A DFA that accepts strings with numerical value that is amultiple of 329

Example 5 (continued)Assume x is portion of the input string being read so far.Let [x] be the numerical value of x, e.g., if x 0010, then[x] 2.Entering state qi means that the string read so far has anumerical value that has a remainder of i when divided by 3.I Case 0: The current state is q0 , then [x] 3k. If the nextsymbol is 0, then [x0] 2 · 3k 6k , a multiple of 3. So thenext state should be q0 . But if the next symbol is 1, then[x1] 2 · 3k 1 6k 1, with a remiander of 1 whendivided by 3. So the next state should be q1 .δ(q0 , 0) q0 , δ(q0 , 1) q1I Case 1: Similar to Case 0. δ(q1 , 0) q2 , δ(q1 , 1) q0I Case 2: Similar to above. δ(q2 , 0) q1 , δ(q2 , 1) q230

A Quick Review of DFAsI Definitions of δ : Q Σ Q and ˆδ : Q Σ QI The language of DFA M, L(M) {w {0, 1} ˆδ(w) F )I A language accepted by a DFA is a regular languageI In designing a DFA with n nodes and alphabet Σ, thefollowing two properties must be satisfied:I (1) each node must have Σ out-going arcsI (2) the total number of arcs must be n · Σ I A dead-end state may be added to a DFA to satisfy theabove propertiesI An example of including a dead-end state in a DFA thataccepts strings that start with a 0:10102010,1DE0,131

2.3 NFA (Sipser 1.2, pp. 47-54)I NFA N (Q, Σ, δ, q0 , F ), whereIIIIIQ is a finite set of states,Σ is an alphabet,q0 Q is the start state,F Q is a set of accept/final states, andδ : Q (Σ {ε}) 2Q is a transition function, whereδ(q, a) P is the set of states that N may enter if thecurrent state is q and the current symbol is a.In the case of δ(q, ε) P, N ignores the current symbol andgoes from q to any state in P without reading any symbol.32

I ε-closure: For any P Q, E(P) is the set of all statesreachable from any state in P via 0 ε-transitions.I Extending δ to ˆδ : Q Σ 2Q : For any q Q and anyw xa Σ , defineIIˆδ(q, ε) E({q}) andˆδ(q, w) E( k δ(pi , a)) if w xa andi 1ˆδ(q, x) {p1 , . . . , pk }.I Language of NFA N: L(N) {w ˆδ(q0 , w) F 6 0}./I How does an NFA accept a string? Among all paths fromq0 to qf F , there is some path such that theconcatenation of symbols on the path matches the string.33

Example 1: Language of strings that contain substring 111012110, 1310, 1Figure 6: An NFA that accepts strings with substring 11134

Example 2: A {w {0, 1} w has 101 or 11 as substrings}01120, ε0, 1310, 1Figure 7: An NFA that accepts strings with substrings 101 or 11Clarification:I Consider string 001011. There are at least two paths fromq0 to q3I Examples of ε-closure (or E-closure): E({q0 }) {q0 };E({q0 , q1 }) {q0 , q1 , q2 }35

Example 3:B {w {0, 1} w has a 1 in the 3rd position from the right end}01120, 130, 10, 1Figure 8: An NFA that accepts strings with a 1 in the third positionfrom the right end36

Example 4: An NFA that accepts decimal numbers (a numberthat may have or preceding it, but must have a decimalpoint, e.g., .123, 23., 1.2, -1.0).2.0 9ε041 , 0 9.30 90 9Figure 9: An NFA that accepts strings that are decimal numbers withor without signs37

2.4 DFAs NFAs (Sipser 1.2, pp.54-58)Subset construction method: Given NFA N (Q, Σ, δ, q0 , F ),construct a DFA M (Q 0 , Σ, δ0 , q00 , F 0 ) such that L(M) L(N).I Q 0 2Q (power set), i.e., Q 0 contains all subsets of Q.Note that if Q n then Q 0 2n . This is just the worstcase. Since many states in M are inaccessible ordead-end states and thus may be thrown away, so inpractice, Q 0 may be much less than 2n .I q00 E({q0 }).I F 0 {R Q 0 R F 6 0}./0I For each R Q and each a Σ, δ0 (R, a) E( p R δ(p, a)).Definition: Any language that can be accepted by DFA or NFAis called a regular language (RL).Theorem: The equivalence of DFAs, NFAs, and RLs.38

Converting an NFA to a DFA with subset constructionExample 1:NFA0120, 100, 111DFA0,1,210,2,30,1,2,3000310, ε1010,20110,30Figure 10: Converting an NFA to DFA with subset construction39

Example 2:NFADFA010,2101,200,1,2011ε01110220,1φ10Figure 11: Converting an NFA to a DFA400,10

Example 3:NFA012130, 10, 10, 1DFA1000030200230101011011013100012012311Figure 12: Converting an NFA to a DFA with subset construction41

Example 3: (continued)Without using the subset construction method, can a DFA bedesigned to accept all strings that has a 1 in the third positionfrom the right ure 13: Design the same DFA from scratch421

Example 4: A bad case for the subset construction: QN n 1 and QD 2n .00,111n 120,10,10,1n0,1Figure 14: A case that converting an NFA to a DFA causes andexponential increasing of states in the DFA43

2.5 Closure Properties of RL’s (Sisper 1.1, pp. 44-47 and 1.2pp. 58-63)I Union: If A and B are regular, so is A B.I Concatenation: If A and B are regular, so is AB.I Star: If A is regular, so is A . (Need a new start state.)44

I Complementation: If A is regular, so is A (which is Σ A).I Intersection: If A and B are regular, so is A B (which isA B).I Difference: If A and B are regular, so is A B (which isA B.I Reverse: If A is regular, so is AR .I Homomorphism: If A is regular, so is h(A) (which is{h(w) w A} for a homomorphism h : Σ (Σ0 ) ).(Discuss later)I Inverse homomorphism: If A is regular, so is h 1 (A) (whereh 1 (A) {w h(w) A}).45

Example: Prove that A {w {a, b} w is of odd length andcontains an even number of a’s} is regular.I Let A1 {w w is of odd length} Let A2 {w w has aneven number of a’s}I Since DFAs exist to accept A1 and A2 , both are RLsI A A1 A2 . By the CP of RLs under intersection, A1 A2is RL. So A is RLDFA for A1DFA for A2a,baa,bbFigure 15: DFAs for A1 and A246ab

3.1 Definition of REs (Sipser 1.3 (pp. 63-66))Regular expressions (REs) are to represent regular languages.Let L(R) be the language that regular expression R represents.A recursive definition is given below:I Basis: ε and 0/ are REs, and L(ε) {ε} and L(0)/ 0./For any a Σ, a is an RE and L(a) {a}.I Induction: If R1 and R2 are REs, thenIIIIR1 R2 is an RE, with L(R1 R2 ) L(R1 ) L(R2 ),R1 R2 is an RE, with L(R1 R2 ) L(R1 )L(R2 ),R1 is an RE, with L(R1 ) (L(R1 )) , and(R1 ) is an RE, with L((R1 )) L(R1 ).47

Remark:I Precedence order for regular-expression operators: Star,concatenation, and finally union. () may override this order.I Use of R and R k .I Algebraic laws:I R1 R2 R2 R1 , (R1 R2 ) R3 R1 (R2 R3 ), and(R1 R2 )R3 R1 (R2 R3 ).I 0/ R R 0/ R, εR Rε R, 0R/ R 0/ 0,/ andR R R.I R1 (R2 R3 ) R1 R2 R1 R3 and(R1 R2 )R3 R1 R3 R2 R3 .I (R ) R , 0/ ε, R RR R R, and R R ε.48

3.2 Understanding REsI RE is a pattern for all strings in a RL. The goal is to makethe RE as simple and readable as possible. Consider thefollowing examples to simplify REsI 1 10 10 I (0 1 ) (0 1) I ((0 1)(0 1) ) (0 1) 49

Given a language, design its REExample 1: {w has no substring 10}: 0 1 Example 2: {w has even number of 1’s}: (0 10 10 ) 0 Example 3: {w has odd length}: ((0 1)(0 1)) (0 1)Example 4: {w has a 1 in the 3rd or 2nd position from the rightend}: (0 1) 1(0 1)(0 1) (0 1) 1(0 1) (0 1) 1(0 1)((0 1) ε) (0 1) 1(0 1)(0 1 ε)Example 5: A language of strings that consist of alternating 0sand 1s: (01) (10) 0(10) 1(01) .50

Example 7: D {w has odd number of alternating blocks of 0sand 1’s} (Note: ε 6 D)I 0 1 0 D, 0 1 0 1 6 D, 11 00 111 D, 0 11 000 11 0 1 6 DI Observation 1: Odd number of blocks implies strings in Dmust start and end with the same symbol.RE for D based on ob.1: 0(0 1) 0 1(0 1) 1 0 1I Observation 2: Draw boundaries between blocks. Neareach boundary, we see substring 01 or 10. A string in Dmust have equal number of substrings of 01 and 10.I RE for D based on ob.2: 0 (1 0 ) 1 (0 1 ) 51

Example 8: E {w In w, each 1 is immediately preceeded bya 0 and followed by a 0}I Look for substring 010I 0010001000010010 E. Rewrite the string as(001)(0001)(00001)(001)(0) (0 1)(0 1)(0 1)(0 1)(0 )I RE: (0 1) 0 ε or equally correct, 0 (10 ) ε52

Proof of Closure Properties of RLsUnion, concatenation and star:N1N2εN1εεConcatεNN*εεεStarN2An example:ε1Union010,101100 not accepted53000,11100 accepted

RE NFA (Sipser 1.3 pp. 67-69)Since REs are defined recursively, it is suitable to construct theequivalent NFAs recursively.I Basis: NFAs for simple RE: ε, 0,/ and a for a Σ.I Induction: Given the NFAs for REs R1 and R2 , what arethe NFAs for R1 R2 , R1 R2 , and R1 ?Example 1: Converting RE (0 10 10 ) to an NFA00101εFigure 16: Converting a RE to an NFA54

Example 2: Converting RE (00 1) (ε 10 )ε01100Figure 17: Converting a RE to an NFATheorem: DFA, NFA, and RE are equivalent ways to accept orrepresent RLs. In particular, RE NFA, NFA DFA, DFA RE(didn’t discuss in our class)55

4.1 Regular versus nonregular languagesI A {0 1 }I B {0n 1n n 0}I C {w {0, 1} w has an equal number of 0s and 1s}I D {w {0, 1} w has an equal # of substrings 01 and 10}56

Proving nonregularity by pumping lemma (Sisper 1.4 pp.77-82)Theorem (The pumping lemma for regular languages):Let A be a regular language. Then there exists a constant p(the pumping length which depends on A) such that s A with s p, we can break s into three substrings s xyz such that1. y 0;2. xy p; and3. i 0, string xy i z A.(Note: xy 0 z xz, xy 1 z xyz, xy 2 z xyyz)57

How to use the pumping lemma to prove that a language is notregular:I (1)Assume that A is regular by contradiction. (2)Then thepumping lemma applies to A. (3)Let p be the constant inthe pumping lemma. (three steps to start the proof)I Select s A with s f (p) p.I By the pumping lemma, x, y, z such that s xyz with y 0, xy p and xy i z A for any i 0.I For any x, y, z such that s xyz, y 0, and xy p, findi 0 such that xy i z 6 A. A contradiction!58

Example 1 (Sipser p. 80): Prove that B {0n 1n n 0} is notregular.I Assume B is RL. Then PL applies to B. Let p be theconstant in PL.I Select s 0p 1p B with s 2p pI By PL, s 0 . . . 0 1 . . . 1 xyz, y 0 and xy p. {z } {z }ppI Since y 6 ε and xy p, then y 0 0I Choose i 0. Then xy 0 z xz 0p 1p for p0 pI So xy 0 z 6 B. A contradiction to PL. So B is non-R.59

Example 2 (Sipser p. 81): Prove that F {ww w {0, 1} } isnot regular.I Assume F is RL. Then PL applies to F . Let p be theconstant in PL.I Select s 0p 10p 1 A with s 2p 2 pI By PL, s 0 . . . 0 1 0 . . . 0 1 xyz, y 0, xy p {z } {z }ppI Since y 6 ε and xy p, then y 0 0I Choose i 2. Then xy 2 z xyyz 0p 10p 1 for p0 pI So xy 2 z 6 F . A contradiction to PL. So F is non-R.60

Example 3: Prove that A {1r r is a prime} is not regular.I Some strings in A: 11, 111, 11111, 1111111, etc.I Assume A is RL. Then PL applies. Let p be the constant.I Select s 1q , where q is a prime and q pI By PL, s 1 . . . 1 xyz, x 1l1 (l1 0), y 1l2 (l2 0), {z }qz 1q l1 l2I By PL, i 0, xy i z 1l1 i·l2 (q l1 l2 ) 1(i 1)l2 q AI Choose i q 1. Then xy i z xy q 1 z 1q(l2 1) 6 AI A contradiction to PL. So A is non-R.61

2Example 4: (Sipser p. 82) Prove that D {1n n 0} is non-R.I Some strings in D: 1, 1111, 111111111, etc.I Assume D is RL. The PL applies. Let p be the constant2I Select s 1p D, s p2 pI By PL, s 1 . . . 1 xyz, x 1l1 (l1 0), y 1l2 (l2 0), {z }p2p2 l1 l2z 1, and l2 xy pI by PL, i, xy i z DI Choose i 2. Consider xy 2 z l1 2l2 (p2 l1 l2 ) l2 p2 . A perfect square?I Some algebra:p2 0 p2 (l2 p2 ) p p2 1 2p p2 (p 1)2p2 xy 2 z (p 1)2 . So xy 2 z is not a perfect square.Then xy 2 z 6 D. A contradiction to PL. So D is non-R.62

Example 5: Prove that A {10n 1n n 0} is not regular.I Assume A is RL. The PL applies. Let p be the constant.I Select s 10p 1p A. s 2p 1 pI By PL, s 1 0 . . . 0 1 . . . 1 xyz, y 0, xy p {z } {z }ppI By PL, i, xy i z A. Consider two cases for y.I Case 1. y contains the first 1: x ε, y 10 .0Choose i 0. xy 0 z xz 0p 1p 6 A, for p0 pI Case 2. y does not contain the first 1: x 10 , y 0 .0Choose i 0. xy 0 z xz 10p 1p 6 A, for p0 pI For both cases, we have found contradiction to PL. So A isnon-R.63

Example 6: Prove that A {(01)a 0b a b 0} is not regular.I Assume A is RL. The PL applies. Let p be the constant.I Select s (01)p 0p 1 A. s 3p 1.I By PL, s 01 . . . 01 0 . . . 0 xyz, y 0, xy p {z } {z }2pp 1I Consider y which is entirely in (01)p .I Case 1: Even length, i.e., y 01 . . . 01 or y 10 . . . 10.Choose i 0 to remove at least a substring 01 or 10,violating a bI Case 2: Odd length, i.e., y 01 . . . 10 or y 10 . . . 01 ory 0 or y 1. Choose i 2 to create substrings of 00 or11, which is not allowed .I In each case listed, we can find an i such that xy i z 6 A. Acontradiction to the PL. So A is non-R.64

4.2 Prove nonregularity by closure propertiesTo prove that A is non-regular, assume it is regular. Find aregular language B and a language operator that preservesregularity, and then apply the operator on A and B to get aregular language C. If C is known to be non-regular, acontradiction is found.Example 1: Prove thatA {w {0, 1} w has an equal # of 0s and 1s} is not regular.I Assume A is regularI Let B {0 1 }. B is known to be RLI Let C A B {0n 1n }. C is known to be non-RI But C is regular by CP under intersectionI A contradiction! So A is non-R65

Example 2: Prove that A {0m 1n m 6 n} is not regular.I Assume A is RLI {0 1 } {0n 1n } A (two disjoint sets)I {0n 1n } {0 1 } AI Since {0 1 } and A are both RL, the difference of the twoRLs is still RL by CP.I So {0n 1n } is RL. A contradiction.I A is non-R66

Example 3: Prove that A {am bn c m n m, n 0} is non-RAbout homomorphism:h : Σ (Σ1 ) , e.g., h(a) 01, h(b) 0, h(c) εh : Σ (Σ1 ) , e.g., h(ab) 010h : h(A) {h(w) w A}I Assume A is RL.I Define homomorphism h such that h(a) 0, h(b) 0,h(c) 1I h(A) {0m 0n 1m n } {0m n 1m n } {0n 1n }I By CP under homomorphism, since A is RL, so is {0n 1n }I A contradiction. So A is non-R67

5.1 Context-free grammars (Sipser 2.1 pp. 100-105)I CFG G (V , Σ, R, S), where V is the set of variables, Σ isthe set of terminals (alphabet), R is the set of rules in theform of V (V Σ) (head body), and S V is the startvariable.I The CFG that generates all palindromes (strings that readthe same forward and backward) over {0, 1} isG ({S}, {0, 1}, R, S), where R containsS 0S0 1S1 0 1 ε.I Any language that can be generated by a CFG is calledcontext-free.68

I Let u, v , w be strings in (V Σ) . If A w is a rule, thenuAv yields uwv , written uAv uwv . We say u derives v , written u v , if u1 , . . . , uk (V Σ) such thatu u1 · · · uk v . Here, means one step and means zero or more steps. I Leftmost and rightmost derivations: , , , .lmrmlm I The language of a CFG G, L(G) {w Σ S w}.L(G) is said to be a CFL.69rm

Some Simple CFGs and their CFLsExample 1: L {0n 1n n 0} a context-free language. It canbe generated by the following context-free grammar.S 0S1 ε.Example 2: Given a CFG G, describe L(G).S AA, A AAA bA Ab aLeftmost derivation: S AA bAA baA baaRightmost derivation: S AA Aa bAa baaL(G) {w {a, b} w has an even (nonzero) number of a0 s}.Example 3: A CFG for simple expressions in programminglanguages:S S S S S (S) II Ia Ib I0 I1 a b70

5.2 Parse trees and ambiguitySS00S1SS IS* SSεaII(a)(b)baS*SS SSIIIaab1(c)Figure 18: Parse trees and ambiguity(a) Parse tree and derivation S 0S1 00S11 0011(b) and (c) Two parse trees (or derivations) for string a b a.71

Parse treesI A parse tree is a tree representation for a derivation, inwhich each interior node is a variable, each leaf node iseither a terminal, or ε, and if an interior node is a variable Aand its children are X1 , . . . , Xk , then there must be a ruleA X1 · · · Xk .I Yield of a parse tree: Concatenation of the leaf nodes in aparse tree rooted at the start variable.I Four equivalent notions: 1. S w; 2. S w;lm 3. S w; andrm4. A parse tree with root S and yield w.72

Ambiguity in grammars and languages (Sipser 2.1 pp.105-106)I A CFG G (V , Σ, R, S) is ambiguous if there is w Σ forwhich there are at least two parse trees (or leftmostderivations).I Grammar G: S S S S S (S) I and I Ia Ib I0 I1 a bis ambiguous since a b a has two parse trees.I Some ambiguous grammars have an equivalentunambiguous grammar. For example, an unambiguousgrammar for the simple expressions is G0 : S S T T ,T T F F , F (S) I, and I Ia Ib I0 I1 a b.73

I A context-free language is said to be inherently ambiguousif all its grammars are ambiguous.I There is no algorithm to determine whether a given CFG isambiguous. There is no algorithm to remove ambiguityfrom an ambiguous CFG. There is no algorithm todetermine whether a given CFL is inherently ambiguous.74

Chomsky normal form (Sipser 2.1 pp. 106-109)The Chomsky Normal Form (CNF): Any nonempty CFL withoutε has a CFG G in which all rules are in one of the following twoforms: A BC and A a, where A, B, C are variables, and a isa terminal. Note that one of the uses of CNF is to turn parsetrees into binary trees.75

5.3 More CFGs designExample 1: {am bn c m n m, n 0}I Rewrite the pattern as am bn c n c mI S aSc T , T bTc εExample 2: {am bm c n d n m, n 0} {am bn c n d m m, n 0}I S S1 S2I S1 AB, A aAb ε, B cBd εI S2 aS2 d C, C bCc ε76

Example 3: {0m 1n m 6 n}I Rewrite the language as {0m 1n m n} {0m 1n m n},which is {0m 1n m 1m } {0n 0m n 1n }I S S1 S2I S1 0S1 1 A, A 1A 1I S2 0S2 1 B, B 0B 077

Example 4: {ai bj i 6 j and 2i 6 j}j ii j 2iij 2i2iFigure 19: Intervals that j falls inI Three languages: aj a bj , ?, ai b b2iI S S1 S2 S3I S1 aS1 b A, A aA aI S2 aS2 b aS2 bb aabbbI S3 aS3 bb B, B bB b78

Example 5: L {ai bj c k {a, b, c} i j 6 k}The grammar will pair a and c until running out one of the two.Then the grammar will consider the following cases.L L1 L2 L3I Case 1: i k. Then j 6 0, i.e., j 1. So L1 {ai b c i }I Case 2: i k. Then j 0. So L2 {ak a b c k }I Case 3: i k. And j 6 k i. So L3 {ai bj

I Finite automata are the simplest computational models for computers with an extremely limited amount of memory. I Use of automata theory in software applications includes: study of the behavior of digital circuits, lexical analyzer in compilers, text

Related Documents:

Deterministic Finite Automata plays a vital role in lexical analysis phase of compiler design, Control Flow graph in software testing, Machine learning [16], etc. Finite state machine or finite automata is classified into two. These are Deterministic Finite Automata (DFA) and non-deterministic Finite Automata(NFA).

Complexity, the Central Concepts of Automata Theory - Alphabets, Strings, Languages, Problems. Deterministic Finite Automata, Nondeterministic Finite Automata, an application: Text Search, Finite Automata with Epsilon-Transitions, Finite automata with output - Mealy and Moore machines, Equivalence of Mealy and Moore machines.

Advanced Automata Theory is a lecture which will rst review the basics of formal languages and automata theory and then give insight into speci c topics from wider area of automata theory. In computer science, automata are an important tool for many theoretical results and various types of automata

properties of bipolar general fuzzy switchboard automata are discussed in term of switching and commutative by proving the theorems that are related into these concepts. . 2.3 Automata theory 18 2.4 Optimisation problems 23 2.4.1 Critical path problem 23 . Deterministic finite automata FSM - Finite state machine FSA - Finite state automata .

Finite Set Automata:- Formal Definition, Finite State Machine, Deterministic Finite Automata . "Introduction to Automata Theory, Languages and Computation", 3rd Edition,2006 4. Anand Sharma, "Theory of Automata and Formal language", Laxmi Publications, 2nd . Packet Switching Network, Frame Relay Network, ATM Protocol Architecture .

Automata and Formal Languages II Tree Automata Peter Lammich SS 2015 1/161. Overview by Lecture Apr 14: Slide 3 Apr 21: Slide 2 Apr 28: Slide 4 May 5: Slide 50 . Finite tree automata: Basic theory (TATA Ch. 1) Pumping Lemma, Clo

Switching and automata theory Language theory and formal semantics Operating Systems Background to Distributed Computing: . Finite automata; Pushdown automata; Linear-bounded automata. PODC 2008, Toronto, Canada, August 20, 2008 Evolution of Distributed Computing Theory. Outline

Electromagnetics and Applications - MIT OpenCourseWare . Preface - ix -