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.

• Automata Theory
• Regular Languages
• Finite Automata
• Turing Machines
• Computational Models

dav_wie Follow

Uploaded on Oct 03, 2024 | 0 Views

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.

Presentation Transcript

1. Theory of Automata Course: Topic: Instructor: Theory of Automata Intro and Regular Languages Mr. Muhammad Arif

2. 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

3. Literature Lecture Slides Soft copies (.pdf) Hard copies Research Papers Research papers from magazines/internet [Week#01,02] - Intro to TOA & Regular Expressions 3

4. 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

5. 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

6. 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

7. 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

8. 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

9. 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

10. 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

11. 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

12. Chapter 1: Introduction to Theory of Automata and Regular Expressions [Week#01,02] - Intro to TOA & Regular Expressions 12

13. What Does Automata Mean? [Week#01,02] - Intro to TOA & Regular Expressions 13

14. What Does Automata Mean? [Week#01,02] - Intro to TOA & Regular Expressions 14

15. What Does Automata Mean? [Week#01,02] - Intro to TOA & Regular Expressions 15

16. What Does Automata Mean? [Week#01,02] - Intro to TOA & Regular Expressions 16

17. [Week#01,02] - Intro to TOA & Regular Expressions 17

18. [Week#01,02] - Intro to TOA & Regular Expressions 18

19. What Does Automata Mean? [Week#01,02] - Intro to TOA & Regular Expressions 19

20. What Does Automata Mean? [Week#01,02] - Intro to TOA & Regular Expressions 20

21. 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

22. 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

23. Finite Automaton [Week#01,02] - Intro to TOA & Regular Expressions 23

24. Pushdown Automaton [Week#01,02] - Intro to TOA & Regular Expressions 24

25. Turing Machine [Week#01,02] - Intro to TOA & Regular Expressions 25

26. Power of Automata [Week#01,02] - Intro to TOA & Regular Expressions 26

27. 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

28. 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

29. 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

30. 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

31. 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

32. 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

33. 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

34. 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

35. 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

36. 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

37. 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

38. 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

39. 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

40. 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

41. 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

42. 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

43. 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

44. 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

45. 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

46. 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

47. 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

48. 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

49. 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

50. 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

Load More ...