tailieunhanh - Automata and Formal Language (chapter 1)

Chương 1 của bộ Slide tiếng Anh môn học lý thuyết automata và ngôn ngữ hình thức đầy đủ của trường ĐHBK . Bộ Slide này có tổng cộng 7 chương. | Automata and Formal Language Quan Thanh Tho qttho@ Course Overview An introduction to the fundamental theories and algorithms for computing on digital computer. Automation: A model producing input from acceptable output based on self-made decision Formal Language: An abstraction of programming language syntax. Course Outline Chapter 1: Introduction Chapter 2: Finite Automata Chapter 3: Regular Language and Regular Grammar Chapter 4: Properties of Regular Language Chapter 5: Context-Free Grammar Chapter 6: Simplification of Context-Free Grammar Chapter 7: Pushdown Automata Reading Materials Giáo trình lý thuyết automat và ngôn ngữ hình thức. Hồ Văn Quân An introduction to formal languages and automata. Peter Linz Introduction to automata theory, languages, and computation. John Hopcroft & Jeffrey Ullman Assessment Assignment: 30% Final Exam: 70% Related Issues Digital Circuit Design Compiler Programming Languages Required Background Set and Graph Theory Induction and . | Automata and Formal Language Quan Thanh Tho qttho@ Course Overview An introduction to the fundamental theories and algorithms for computing on digital computer. Automation: A model producing input from acceptable output based on self-made decision Formal Language: An abstraction of programming language syntax. Course Outline Chapter 1: Introduction Chapter 2: Finite Automata Chapter 3: Regular Language and Regular Grammar Chapter 4: Properties of Regular Language Chapter 5: Context-Free Grammar Chapter 6: Simplification of Context-Free Grammar Chapter 7: Pushdown Automata Reading Materials Giáo trình lý thuyết automat và ngôn ngữ hình thức. Hồ Văn Quân An introduction to formal languages and automata. Peter Linz Introduction to automata theory, languages, and computation. John Hopcroft & Jeffrey Ullman Assessment Assignment: 30% Final Exam: 70% Related Issues Digital Circuit Design Compiler Programming Languages Required Background Set and Graph Theory Induction and Contradiction-based Methods Three Basic Concepts Languages Grammars Automata Languages Alphabet: a finite and nonempty set of symbols = {a, b} Example Roman Alphabet: A,B,C,,Z. Greek Alphabet: , , Language (cont’d) String: finite sequence of symbols from : empty string *: the set of all strings on ( + = * { }) Example : Given = {a,b} => * = { , a, b, aa, ab, ba, aaa, .} w = abaaa is a string of L = {anbn | n 0} = { , ab, aabb, .} is a set of strings of Language (cont’d) Language: a subset L of * Sentence: a string in L Example : In Example , L is a language on , w is a string of but not a sentence in L Language Concatenation L1L2 = {xy | x L1, y L2} Ln = L L . L (n times) L0 = { } Language Concatenation (cont’d) Example : L = {anbn | n 0} L2 = {anbnambm | n 0, m 0} Closure Operators Star-Closure: L* = L0 L1 L2 . Positive-Closure: L+ = L1 L2 . Grammar Grammar for a natural language: a set of rules to construct vocabulary .