Theory of Automata: Introduction and Regular Languages Overview
This course delves into the fundamentals of Theory of Automata, exploring topics such as regular languages, finite state models, grammars, Turing machines, and more. Instructor Mr. Muhammad Arif guides students through essential concepts like finite automata, pumping lemma, decidability, and Chomsky's hierarchy of grammars. The purpose of the course is to understand the theoretical underpinnings of computing beyond hardware and software, focusing on the capabilities and limitations of different computational models. By studying mathematical machines and analyzing their strengths and weaknesses, students aim to identify the most powerful computational model, despite recognizing that no machine can perform every task. The course content includes lectures, assessment criteria, literature resources, and an in-depth exploration of automata theory and regular expressions.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Theory of Automata Course: Topic: Instructor: Theory of Automata Intro and Regular Languages Mr. Muhammad Arif
Course Assessment Criteria 50% 25% Final Exam Midterm Quizzes 4 best quizzes out of 6 Assignments Presentation + Report Total 10% 10% 05% 100% [Week#01,02] - Intro to TOA & Regular Expressions 2
Literature Lecture Slides Soft copies (.pdf) Hard copies Research Papers Research papers from magazines/internet [Week#01,02] - Intro to TOA & Regular Expressions 3
Course contents in brief Finite State Models: Language definitions preliminaries Regular expressions/Regular languages, Finite automata (FAs), Transition graphs (TGs), NFAs, kleene s theorem, Transducers (automata with output), Pumping lemma and non regular language Grammars and PDA Context free grammars, Derivations, derivation trees and ambiguity, Simplifying CFLs, Normal form grammars and parsing, Push-down Automata, Pumping lemma and non-context free languages, Decidability, Chomsky s hierarchy of grammars Turing Machines Theory: Turing machines, Post machine, Variations on TM, TM encoding, Universal Turing Machine Context sensitive Grammars, Defining Computers by TMs. [Week#01,02] - Intro to TOA & Regular Expressions 4
Purpose of Course In this Course our concern is not with actual hardware and software. More interested in capability of computers. specifically, what can and what cannot be done by any existing computer or any computer ever built in the future. We will study different types of theoretical machines that are mathematical models for actual physical processes. [Week#01,02] - Intro to TOA & Regular Expressions 5
Cont. By considering the possible inputs on which these machines can work,we can analyze their various strengths and weaknesses. We can then develop what we may believe to be the most powerful machine possible. Surprisingly, it will not be able to perform every task. [Week#01,02] - Intro to TOA & Regular Expressions 6
Cont. In particular, the way we shall be studying about computers is to build mathematical models, called machines, and then to study their limitations by analyzing the types of inputs on which they can operate successfully. The collection of these successful inputs is called the language of the machine [Week#01,02] - Intro to TOA & Regular Expressions 7
Cont. Every time we introduce a new machine, we will learn its language; and every time we develop a new language, we will try to find a machine that corresponds to it. We will study different types of theoretical machines that are mathematical models for actual physical processes. By considering the possible inputs on which these machines can work, we can analyze their various strengths and weaknesses. [Week#01,02] - Intro to TOA & Regular Expressions 8
Recommended Books Introduction to Computer Theory, Denial Cohen, John Wiley & Sons, Inc. Theory of Automata By C.J. Martin Introduction to Automata Theory, Languages & Computation, J Hopcraft, D. Ullman Languages & Machines, An Into to the Theory of Computer Science, 2/e Thomas A. Sudkamp, Addison Wesley. [Week#01,02] - Intro to TOA & Regular Expressions 9
Important Issues Attendance policy and late comers Assignments policy All typed assignments Title page: Registration number Course title Assignment name Assignment number Submission date Font size of the headings should be 12, Bold and may be underlined [Week#01,02] - Intro to TOA & Regular Expressions 10
Important Issues Text font size should be 12 Font style should be Times, Arial or Book Antiqua Page numbers Default page settings Table of contents for large assignments (applicable for more than 5 pages) Single spacing Justified No color except black and blue References of the source material used (no copied material will be accepted) [Week#01,02] - Intro to TOA & Regular Expressions 11
Chapter 1: Introduction to Theory of Automata and Regular Expressions [Week#01,02] - Intro to TOA & Regular Expressions 12
What Does Automata Mean? [Week#01,02] - Intro to TOA & Regular Expressions 13
What Does Automata Mean? [Week#01,02] - Intro to TOA & Regular Expressions 14
What Does Automata Mean? [Week#01,02] - Intro to TOA & Regular Expressions 15
What Does Automata Mean? [Week#01,02] - Intro to TOA & Regular Expressions 16
[Week#01,02] - Intro to TOA & Regular Expressions 17
[Week#01,02] - Intro to TOA & Regular Expressions 18
What Does Automata Mean? [Week#01,02] - Intro to TOA & Regular Expressions 19
What Does Automata Mean? [Week#01,02] - Intro to TOA & Regular Expressions 20
What does automata mean? Automata is Greek letters .Automata is a word formulated from automation, which means machine designing or replacing human beings with machines It is the plural of automaton, and it means something that works automatically . [Week#01,02] - Intro to TOA & Regular Expressions 21
Different Kinds of Automata Automata are distinguished by the temporary memory Finite Automata: no temporary memory Pushdown Automata: stack Turing Machines: random access memory [Week#01,02] - Intro to TOA & Regular Expressions 22
Finite Automaton [Week#01,02] - Intro to TOA & Regular Expressions 23
Pushdown Automaton [Week#01,02] - Intro to TOA & Regular Expressions 24
Turing Machine [Week#01,02] - Intro to TOA & Regular Expressions 25
Power of Automata [Week#01,02] - Intro to TOA & Regular Expressions 26
Languages Letters, Words, Sentences Alphabets join to form words Words combine to form sentences Sentences combine to form paragraphs and so on But the matter of fact is not all collections of letters form a valid word and not all collection of words form a valid sentence. [Week#01,02] - Intro to TOA & Regular Expressions 27
Languages How can you tell whether a given sentence belongs to a particular languages Black is cat the The tea is hot I like chocolates two much Rules give a clue to forming as well as validating sentences. There are two types of languages: Formal Languages (Syntactic Languages) Informal Languages (Semantic Languages) [Week#01,02] - Intro to TOA & Regular Expressions 28
Formal vs. Informal Rules Informal language -> abstract languages Incoherent strings are understandable Slang, idiom, dialect etc. But Raise ambiguity Interpretation varies with region I am through (BrE/AmE) Same words have multiple meanings. Like, light, base, etc. [Week#01,02] - Intro to TOA & Regular Expressions 29
Informal languages Natural languages are generally defined informally Human brain are capable to understand incoherent even invalid sentences. You mangoes like We school daily go to Rectify grammatical errors etc. Resolve ambiguity Interpret according to context Supporting aids such as Facial expressions and body language etc. [Week#01,02] - Intro to TOA & Regular Expressions 30
How to Communicate with machines ? Need a language: what sort Machines don t have human mind though may have its partial imitation Would fail on incorrect or ambiguous input Some recovery or input corrections may be proposed but again very limited. Thus need a precise, explicit and universal definition of communication language [Week#01,02] - Intro to TOA & Regular Expressions 31
Summary of Languages Three aspects/specifications Lexical Defines valid words/units of a language Syntactic Defines rules for combining the units to form valid sentences (computer programs in context of machines) Semantic Concerned with the interpretation or meaning of a sentence (what output to produce in context of machines) Affected by ambiguity the most. [Week#01,02] - Intro to TOA & Regular Expressions 32
Formal Languages Word formal refers to the fact that all the rules for the language are explicitly stated in terms of what string of symbols can occur No ambiguities Universally uniform understanding Let the machine Interpret an input uniformly every time. i.e. always produces same output for a particular input Avoid crashes because of ambiguity Explicitly reject invalid input [Week#01,02] - Intro to TOA & Regular Expressions 33
Formal Languages Need precise uniformly understandable notation Representations Alphabet Represents a finite set of fundamental units of lanauges, e.g. for English ={a,b, .z.A, Z,} Denoted by = {0,1} = {0,1,2,3,4,5,6,7,8,9} A certain specified set of strings of characters from the alphabet is called the language (set of words) [Week#01,02] - Intro to TOA & Regular Expressions 34
Formal Languages List of words Set of all valid words of a given language, e.g., a language English_Words that contains all valid words of English would have a = {all entries of the dictionary + punctuation marks and blank space} Denoted by Is Finite or Infinite set. Strings: Concatenation of finite symbols from the alphabets is called a string. A string a finite sequence of symbols chosen from alphabet. Example: if ={a,b} then a, abab, aaab, ababababa . [Week#01,02] - Intro to TOA & Regular Expressions 35
Formal Languages Empty String or Null String Empty String is a string which does not contain any letter. It is same as the empty set. It is denoted by capital Greek letter lambda . Words In spoken languages not all strings are words. Example: in English if we combine abcd, it does not form any word. Words are strings belonging to some language. Example: if ={x} then a language L can be defined as, L={xn: n=1,2,3 } OR L={x, xx, xxx, xxxx ..} Here x, xx, xxx . are the words of L. Note: Not all strings are words but all words are strings [Week#01,02] - Intro to TOA & Regular Expressions 36
Formal Languages Valid/In-valid Alphabets While defining an alphabets, an alphabet may contain letters consisting of group of symbols, e.g., consider 2 alphabets: 1={B, aB, bab, d} and 2={B, Ba, bab, d} and a string BababB This string may be tokenized in two different ways: (Ba), (bab), (B) (B), (abab), (B) Which shows that the 2nd group can not be identified as a string, defined over = {a,b} [Week#01,02] - Intro to TOA & Regular Expressions 37
Formal Languages Note While defining an alphabet of letters consisting of more than one symbols, no letter should be started with the letter of the same alphabet i.e. one letter should not be the prefix of another. However, a letter may be ended in the letter of same alphabet i.e. one letter may be the suffix of another. Therefore, 1 is a valid alphabet and 2 is in-valid alphabet. [Week#01,02] - Intro to TOA & Regular Expressions 38
Formal Languages String Variable: A letter used for denoting a string. The author uses w, x, y and z as string variable. For example w = 0111100 , x = 123045, z = abbbcdeg String Length: The number of positions for symbols in the string. For simplicity we can say that it is the number of symbols in the string. For example |w| = 7 , |x| = ? , |z| = ? [Week#01,02] - Intro to TOA & Regular Expressions 39
Formal Languages Reverse of a string The reverse of a string s, denoted by rev(s), is obtained by writing the letters of s in reverse order. Example 1: if s=abc is a string defined over ={a,b,c} then Rev(s)= cba Example 2: if s=BaBbabBd is a string defined over ={B,aB,bab,d} then Rev(s)= dBbabaBB [Week#01,02] - Intro to TOA & Regular Expressions 40
Defining Languages The language can be defined in different ways, such as Descriptive definition Recursive definition Using Regular expressions (RE) and Using Finite automaton (FA) etc. [Week#01,02] - Intro to TOA & Regular Expressions 41
Defining Languages Define alphabet set Define rules for forming valid words and sequences of words from Called grammar Can be descriptive Limitations of informalism Can be mathematical Can also define supporting functions e.g., length(X), reverse(x) [Week#01,02] - Intro to TOA & Regular Expressions 42
Defining languages Example ={a,b, z} L = {all words formed only of odd number of xs} L = {xn | n is odd} L = {all words of length less than or equal to 4} PALINDROME ={ , all strings x such that reverse (x) = x} [Week#01,02] - Intro to TOA & Regular Expressions 43
Finite vs. Infinite Languages Finite Languages Countable set of words Can be defined by rigorously listing the words in E.g. English_Words Infinite Languages Infinite set of valid words Cant be listed completely E.g. English_Sentences [Week#01,02] - Intro to TOA & Regular Expressions 44
Infinite Languages Most of the languages are infinite How can u check whether a word belongs to a language if it is Finite Checking its entry in Infinite Validating against rules [Week#01,02] - Intro to TOA & Regular Expressions 45
Defining Language Define alphabet set Define rules for forming valid words and sequences of words from This is called grammar Can be descriptive Limitations of informalism Can be mathematical Can also define supporting functions e.g., length(X), reverse(x) [Week#01,02] - Intro to TOA & Regular Expressions 46
bilawalsheikh333.blogspot.com Theory of Automata (BSCS)-4A Fall 2012, BU Islamabad Defining Languages Language defining rules can be of two kinds; 1. They can either tell us how to test a string of alphabet letters that we might be presented with, to see if it is a valid word or 2. They can tell us how to construct all the words in the language by some clear procedures (discussed later) [Week#01,02] - Intro to TOA & Regular Expressions 47
bilawalsheikh333.blogspot.com Theory of Automata (BSCS)-4A Fall 2012, BU Islamabad Defining Languages Example Lets discuss a simple example of language, if we start with an alphabet having only one letter, the letter x = {x} We can define a language by saying any nonempty string of alphabet characters L = {x xx xxx xxxx } L = {x^n for n =1, 2, 3, } Because of the way we have defined it, this language does not include the null string ( ) [Week#01,02] - Intro to TOA & Regular Expressions 48
bilawalsheikh333.blogspot.com Theory of Automata (BSCS)-4A Fall 2012, BU Islamabad Defining Languages We can define the operation of concatenation xn concatenated xm is the new word xn+m We can define a language that contain L = { , x, xx, xxx, xxxx} = {xnfor n = 0, 1, 2, 3, } Here x0= and not x0 =1 [Week#01,02] - Intro to TOA & Regular Expressions 49
bilawalsheikh333.blogspot.com Theory of Automata (BSCS)-4A Fall 2012, BU Islamabad Defining Languages The language can be defined in different ways, such as Descriptive definition Recursive definition Using Regular expressions (RE) and Using Finite automaton (FA) etc. [Week#01,02] - Intro to TOA & Regular Expressions 50
