Understanding Computer Theory: From Automata to Turing Machines
Dive into the world of computer theory, exploring concepts like automata, formal languages, and Turing machines. Learn about pioneers like Alan Turing and the fundamental questions in computer science, from computability to complexity.
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
Computer Theory Introduction
A simple computer f on start off BATTERY f input: switch bulb is on if and only if there was an odd number of flips output: light bulb actions:ffor flip switch states:on, off
Another computer 1 off 1 start off 1 2 2 2 2 BATTERY 1 2 on off 1 inputs: switches 1 and 2 bulb is on if and only if both switches were flipped an odd number of times actions:1for flip switch 1 actions: 2for flip switch 2 states:on, off
Theory of Automata finite automata Devices with a finite amount of memory. Used to model small computers. push-down automata Devices with infinite memory that can be accessed in a restricted way. Used to model parsers, etc. Turing Machines Devices with infinite memory. Used to model any computer. time-bounded Turing Machines Infinite memory, but bounded running time. Used to model any computer program that runs in a reasonable amount of time.
Alan Turing (1912-1954) (A pioneer of automata theory) Father of Modern Computer Science English mathematician Studied abstract machines called Turing machines even before computers existed Heard of the Turing test?
What is Automata Theory? Study of abstract computing devices, or machines Automaton = an abstract computing device A device need not even be a physical hardware! A fundamental question in computer science: Find out what different models of machines can do and cannot do The theory of computation Computability vs. Complexity
Introduction to Computer Theory What does automata mean? It is the plural of automaton, and it means something that works automatically Introduction to languages There are two types of languages Formal Languages (Syntactic languages) Informal Languages (Semantic languages)
Alphabets A finite non-empty set of symbols (called letters), is called an alphabet. It is denoted by ( Greek letter sigma) Example = {a, b} = {0, 1} (language understood by computers) = {i, j, k}
Strings Concatenation of finite number of letters from the alphabet is called a string. Example If = {a, b} then a, abab, aaabb, ababababababababab Empty string or null string Sometimes a string with no symbol at all is used, denoted by (Small Greek letter Lambda) or (Capital Greek letter Lambda) , is called an empty string or null string.
Words 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, ...}. Here x, xx , are the words of L All words are strings, but not all strings are words.
Length of Strings The length of string s, denoted by |s|, is the number of letters in the string. Example: = {a,b}, s = ababa, |s| = 5 = {B, aB, bab, d}, s = BaBbabBd, Tokenizing = (B), (aB), (bab), (B), (d) |s|=5
Reverse of a String The reverse of a string s denoted by Rev(s) or sr, is obtained by writing the letters of s in reverse order. Exmaple: If s = abc is a string defined over = {a, b, c} then Rev(s) or sr = cba = {B, aB, bab, d}, s = BaBbabBd, Rev(s) = dBbabaBB
Defining Languages The languages can be defined in different ways: Descriptive definition Recursive definition Regular Expressions(RE) Finite Automaton(FA) Descriptive definition of language The language is defined, describing the conditions imposed on its words.
Examples The language L of strings of odd length, defined over ={a} L = {a, aaa, aaaaa, ..} The language L of strings that does not start with a, defined over ={a,b,c} L = {b, c, ba, bb, bc, ca, cb, cc, } The language L of strings of length 2, defined over ={0,1,2} L = {00, 01, 02, 10, 11, 12, 20, 21, 22}
Examples The language L of strings ending in 0, defined over ={0,1} L = {0, 00, 10, 000, 010, 100, 110, } The language EQUAL, of strings with number of a s equal to number of b s, defined over ={a,b}, L = { , ab, aabb, abab, baba, abba, }
Examples The language EVEN-EVEN, of strings with even number of a s and even number of b s, defined over ={a,b}, L = { , aa, bb, aaaa,aabb,abab, abba, baab, baba, bbaa, bbbb, } The language INTEGER, of strings defined over ={-,0,1,2,3,4,5,6,7,8,9} INTEGER = { ,-2,-1,0,1,2, }
Examples The language EVEN, of stings defined over ={-, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9} EVEN = { , -4, -2, 0, 2, 4, } The language {anbn }, of strings defined over ={a,b}, as {anbn: n=1, 2, 3, } L = {ab, aabb, aaabbb, aaaabbbb, }
Examples The language {anbnan }, of strings defined over ={a,b}, as {anbnan: n=1, 2, 3, } L = {aba, aabbaa, aaabbbaaa, aaaabbbbaaaa, } The language factorial, of strings defined over ={0, 1, 2, 3, 4, 5, 6, 7, 8, 9} L = {1,2,6,24,120, } The language FACTORIAL, of strings defined over ={a}, as {an! : n=1,2,3, }, can be written as L = {a, aa, aaaaaa, }
Examples The language DOUBLEFACTORIAL, of strings defined over ={a, b}, as {an!bn! : n=1,2,3, } L = {ab, aabb, aaaaaabbbbbb, } The language SQUARE, of strings defined over ={a}, as {an*n: n=1,2,3, } L = {a, aaaa, aaaaaaaaa, }
Examples The language DOUBLESQUARE, of strings defined over ={a,b}, as {an*n bn*n : n=1,2,3, } L = {ab, aaaabbbb, aaaaaaaaabbbbbbbbb, } The language PRIME, of strings defined over ={a}, as {ap : p is prime} L = {aa, aaa, aaaaa, aaaaaaa, aaaaaaaaaaa, }
PALINDROME The language consisting of and the strings s defined over such that Rev(s)=s. The words of PALINDROME are called palindromes. For = {a, b} PALINDROME = { , a, b, aa, bb, aaa, aba, bab, bbb, ...}
Kleene Star Closure Given , then the Kleene Star Closure of the alphabet , denoted by *, is the collection of all strings defined over , including . Kleene Star Closure can be defined over any set of strings. Examples If = {x} Then * = { , x, xx, xxx, xxxx, .} If = {0,1} Then * = { , 0, 1, 00, 01, 10, 11, .} If = {aaB, c} Then * = { , aaB, c, aaBaaB, aaBc, caaB, cc, .} Languages generated by Kleene Star Closure of set of strings, are infinite languages. (By infinite language, it is supposed that the language contains infinite many words, each of finite length).
PLUS Operation (+) Plus Operation is the same as Kleene Star Closure except that it does not generate (null string). If = {0, 1} Then += {0, 1, 00, 01, 10, 11, .} If = {aab, c} Then += {aab, c, aabaab, aabc, caab, cc, .} Kleene Star can also be operated on any string i.e. a* can be considered to be all possible strings defined over {a}, which shows that a* generates , a, aa, aaa, a+ can be considered to be all possible non empty strings defined over {a}, which shows that a+ generates a, aa, aaa, aaaa,
Recursive definition of languages The following three steps are used in recursive definition 1. Some basic words are specified in the language. 2. Rules for constructing more words are defined in the language. 3. No strings except those constructed in above, are allowed to be in the language Example: Defining language of INTEGER Step 1: 1 is in INTEGER. Step 2: If x is in INTEGER then x+1 and x-1 are also in INTEGER. Step 3: No strings except those constructed in above, are allowed to be in INTEGER.
Examples Defining language of EVEN Step 1: 2 is in EVEN. Step 2: If x is in EVEN then x+2 and x-2 are also in EVEN. Step 3: No strings except those constructed in above, are allowed to be in EVEN. Defining the language factorial Step 1: As 0!=1, so 1 is in factorial. Step 2: n!=n*(n-1)! is in factorial. Step 3: No strings except those constructed in above, are allowed to be in factorial.
Examples Defining the language {anbn}, n=1,2,3, , of strings defined over ={a,b} Step 1: ab is in {anbn} Step 2: if x is in {anbn}, then axb is in {anbn} Step 3: No strings except those constructed in above, are allowed to be in {anbn} Defining the language L, of strings ending in a , defined over ={a,b} Step 1: a is in L Step 2: if x is in L then s(x) is also in L, where s belongs to * Step 3: No strings except those constructed in above, are allowed to be in L
Examples Defining the language L, of strings beginning and ending in same letters , defined over ={a, b} Step 1: a and b are in L Step 2: (a)s(a) and (b)s(b) are also in L, where s belongs to * Step 3: No strings except those constructed in above, are allowed to be in L Defining the language L, of strings containing aa or bb , defined over ={a, b} Step 1: aa and bb are in L Step 2: s(aa)s and s(bb)s are also in L, where s belongs to * Step 3: No strings except those constructed in above, are allowed to be in L
Examples Defining the language L, of strings containing exactly one a, defined over ={a, b} Step 1: a is in L Step 2: s(aa)s is also in L, where s belongs to b* Step 3: No strings except those constructed in above, are allowed to be in L Defining the language PALINDROME, defined over = {a, b} Step 1: a and b are in PALINDROME Step 2: if x is palindrome, then s(x) Rev(s) and xx will also be palindrome, where s belongs to * Step 3: No strings except those constructed in above, are allowed to be in palindrome
Regular Expression a* generates , a, aa, aaa, and a+ generates a, aa, aaa, aaaa, , so the language L1 = { , a, aa, aaa, } and L2 = {a, aa, aaa, aaaa, } can simply be expressed by a* and a+, respectively. a* and a+ are called the regular expressions (RE) for L1 and L2 respectively. a+, aa* and a*a generate L2.
Recursive definition of RE Recursive definition of Regular Expression(RE) Step 1: Every letter of including is a regular expression. Step 2: If r1 and r2 are regular expressions then following are also regular expressions (r1) r1r2 r1 + r2 and r1* Step 3: Nothing else is a regular expression
Examples L={ , x, xx, xxx, } of strings, defined over = {x}. We can write this language as the Kleene star closure of alphabet or L= *={x}* . This language can also be expressed by the regular expression x*. Similarly the language L={x, xx, xxx, }, defined over = {x}, can be expressed by the regular expression x+.
Examples Language L consists of all possible strings, defined over = {a, b}. This language can also be expressed by the regular expression (a + b)* Language L consists of strings having exactly one a, defined over = {a, b}, then it s regular expression may be b*ab*
Examples L consists of even length, defined over = {a, b}, then it s regular expression may be ((a+b)(a+b))* Language L of odd length, defined over = {a, b}, then it s regular expression may be (a+b)((a+b)(a+b))* or ((a+b)(a+b))*(a+b)
Examples A language may be expressed by more than one regular expression, while given a regular expression there exist a unique language generated by that regular expression Language defined over = {a , b} of words having at least one a, may be expressed by a regular expression (a+b)*a(a+b)* Language L defined over = {a, b} of words having at least one a and one b, may be expressed by a regular expression (a+b)*a(a+b)*b(a+b)* + (a+b)*b(a+b)*a(a+b)*
Examples L defined over ={a, b}, of words starting with double a and ending in double b then its regular expression may be aa(a+b)*bb L defined over ={a, b} of words starting with a and ending in b OR starting with b and ending in a, then its regular expression may be a(a+b)*b+b(a+b)*a
Examples Language of strings, defined over ={a, b} having even number of a s and even number of b s. i.e. EVEN-EVEN = { , aa, bb, aaaa,aabb,abab, abba, baab, baba, bbaa, bbbb, }, its regular expression can be written as (aa+bb+(ab+ba)(aa+bb)*(ab+ba))* It is important to be clear about the difference of the following regular expressions r1 = a*+b* r2 = (a+b)* Here r1 does not generate any string of concatenation of a and b, while r2 generates such strings.
Equivalent Regular Expressions Two regular expressions are said to be equivalent if they generate the same language. Example: r1 = (a + b)* (aa + bb) r2 = (a + b)*aa + ( a + b)*bb then both regular expressions define the language of strings ending in aa or bb. If r1 = (aa + bb) and r2 = ( a + b) then r1+r2 = (aa + bb) + (a + b) r1r2 = (aa + bb) (a + b) = (aaa + aab + bba + bbb) (r1)* = (aa + bb)*
Regular Languages The language generated by any regular expression is called a regular language. If r1, r2 are regular expressions, corresponding to the languages L1 and L2 then the languages generated by r1+ r2, r1r2( or r2r1) and r1*( or r2*) are also regular languages If L1 and L2 are expressed by r1and r2, respectively then the language expressed by r1+ r2, is the language L1 + L2 or L1 Union L2 r1r2, , is the language L1L2, of strings obtained by prefixing every string of L1 with every string of L2 r1*, is the language L1*, of strings obtained by concatenating the strings of L, including the null string.
Examples If r1 = (aa+bb) and r2 = (a+b) then the language of strings generated by r1+r2, is also a regular language, expressed by (aa+bb) + (a+b) If r1 = (aa+bb) and r2 = (a+b) then the language of strings generated by r1r2, is also a regular language, expressed by (aa+bb)(a+b) If r = (aa+bb) then the language of strings generated by r*, is also a regular language, expressed by (aa+bb)*
All finite languages are regular Consider the language L, defined over = {a,b}, of strings of length 2, starting with a, then L = {aa, ab}, may be expressed by the regular expression aa+ab. Hence L, by definition, is a regular language. If a language contains even thousand words, its RE may be expressed, placing + between all the words. Here the special structure of RE is not important. Consider the language L = {aaa, aab, aba, abb, baa, bab, bba, bbb}, that may be expressed by a RE aaa+aab+aba+abb+baa+bab+bba+bbb, which is equivalent to (a+b)(a+b)(a+b).
Precedence of Operators Parentheses may be used wherever needed to influence the grouping of operators. Order of precedence is * (highest), then concatenation, then + (lowest).
