COS3701 - SUMMARIZED EXAM NOTES 2021.

COS3701 - SUMMARIZED EXAM NOTES 2021. Theoretical Computer Science III. Theory of Computation 4 Mustansiriya University – college of sciences – computer science department – second class Language language is the set of all strings of terminal symbols derivable from alphabet. alphabet is a finite set of symbols. For example {0, 1} is an alphabet with two symbols, {a, b} is another alphabet with two symbols and English alphabet is also an alphabet. A string (also called a word) is a finite sequence of symbols of an alphabet. b, a and aabab are examples of string over alphabet {a, b} and 0, 10 and 001 are examples of string over alphabet {0, 1}, A null string is a string with no symbols, usually denoted by epsilon or lambda (). A language is a set of strings over an alphabet. Thus {a, ab, baa} is a language (over alphabert {a,b}) and {0, 111} is a language (over alphabet {0,1}). The number of symbols in a string is called the length of the string. For a string w its length is represented by |w| . It can be The empty string (also called null string) it has no symbols. The empty string is denoted by Thus || = 0. For example |00100| = 5, |aab| = 3, | | = 0 Language = alphabet + string (word) + grammar (rules, syntax) + operations on languages (concatenation, union, intersection, Kleene star) Kinds of languages: 1- Talking language: (e.g.: English, Arabic): It has alphabet: ={a,b,c,….z}From these alphabetic we make sentences that belong to the language. Now we want to know is this sentence is true or false so 
We need a grammar. Ali is a clever student. (It is a sentence  English language.) 2- Programming language: (e.g.: c++, Pascal):It has alphabetic:={a,b,c,.z , A,B,C,..Z , ?, /, - ,.} From these alphabetic we make sentences that belong to programming language. Now we want to know if this sentence is true or false so we need a compiler to make sure that syntax is true. 3- Formal language: (any language we want.) It has strings from these strings we make sentences that belong to this formal language. Now we want to know is this sentence is true or false so we need rules. Example: Alphabetic: = {0, 1}. Sentences: , . Rules: Accept any sentence start with zero and refuse sentences that start with one. So we accept: as a sentence satisfies the rules. And refuse: as a sentence doesn't satisfy the rules. Example: Alphabetic: = {a, b}. Sentences: ababaabb, bababbabb Rules: Accept any sentence start with a and refuse sentences that start with b. So we accept: aaaaabba as a sentence satisfies the rules. And refuse: baabbaab as a sentence doesn't satisfy the rules. Theory of Computation 5 Mustansiriya University – college of sciences – computer science department – second class Regular Expression is a set of symbols, Thus if alphabet= {a, b}, then aab, a, baba, bbbbb, and baaaaa would all be strings of symbols of alphabet. In addition we include an empty string denoted by which has no symbols in it. Examples of Kleene star: 1* is the set of strings {, 1, 11, 111, 1111, 11111, etc. } (1100)* is the set of strings {, 1100, , 100, etc. } (00+11)* is the set of strings {epsilon, 00, 11, 0000, 0011, 1100, 1111, , , , etc. } (0+1)* is all possible strings of zeros and ones, often written as sigma * where sigma = {0, 1} (0+1)* (00+11) is all strings of zeros and ones that end with either 00 or 11. (w)+ is a shorthand for (w)(w)* w is any string or expression and the superscript plus, + 1- Concatenation: Notation to the concatenation: . (The dot.): if L1 = {x, xxx} and L2 = {xx} So (L1.L2) means L1 concatenated L2 and it is equal = {xxx, xxxxx} Examples on concatenations: Ex1: L1 = {a, b}. L2 = {c, d}. L1.L2 = {ac, ad, bC, bd} Note: ab differ from ba. Ex2: = {x}. L1 = {set of all odd words over with odd length}. L1 = {set of all even words over with odd length}. L1= {x, xxx, xxxxx, xxxxxxx……}. L2= {, xx, xxxx, xxxxxx…}. L1.L2 = {x, xxx, xxxxx, xxxxxxx…}. Note:  

 

 Ex3: L1 = {x, xxx}. L2 = {xx}. L1.L2 = {xxx, xxxxx}. Some rules on concatenation: .x = x L1.L2 = {set of elements}

Definition of a Regular Expression A regular expression may be the null string, r = A regular expression may be an element of the input alphabet, r = a A regular expression may be the union of two regular expressions, r = r1 + r2 A regular expression may be the concatenation of two regular expressions, r = r1 r2 A regular expression may be the Kleene closure (star) of a regular expression r = r1* A regular expression may be a regular expression in parenthesis r = (r1) Theory of Computation 6 Mustansiriya University – college of sciences – computer science department – second class epsilon is the zero length string 0, 1, a, b, c, are symbols in sigma x is a variable or regular expression ( ... )( ... ) is concatenation ( ... ) + ( ... ) is union ( ... )* is the Kleene Closure = Kleene Star ()(x) = (x)( ) = ()(x) = (x)( ) = x () + (x) = (x) + () = x x + x = x ()* = ()( ) = (x)* + () = (x)* = x* (x + )* = x* x* (a+b) + (a+b) = x* (a+b) x* y + y = x* y (x + )x* = x* (x + ) = x* (x+ )(x+ )* (x+ ) = x* λ is the null string (there are no symbols in this string) * is the set of all strings of length greater than or equal to 0 Example: A = {a,b} // the alphabet is composed of a and b A* = {λ, a,b,aa,ab,ba,bb,aaa,aab,…} The symbol * is called the Kleene star. ∅ (empty set) λ (empty string) ( ) delimiter , ∪ + union (selection) concatenation Given regular expressions x and y, x + y is a regular expression representing the set of all strings in either x or y (set union) x = {a b} y = {c d} x + y = {a b c d} Mark Hills CS421 Lecture 9: Regular Expressions and Finite Automata Example 1 Let A={0,1}, W1 = , W2 = 00000 W1W2 = 0000 W2W1 = 0011 W1 λ = W1 = λ W2 = W2 = 00000 x = {a b} y = {c d} xy = {ac ad bc bd} Note: ( a + b )* = ( a* b * )* Theory of Computation 7 Mustansiriya University – college of sciences – computer science department – second class Examples of regular expressions Describe the language = what is the output (words, strings) of the following RE Regular expression output(set of strings) λ {λ} λ* {λ} a { a } aa { aa } a* {λ, a, aa, aaa, ….} aa* { a, aa, aaa, ... } a+ { a, aa, aaa, ...} ba+ { ba, baa, baaa, ...} (ba)+ { ba, baba, bababa, ...} (a|b) { a, b } a|b* { a, λ, b, bb, bbb, ... } (a|b)* { λ, a, b, aa, ab, ba, bb, ... } aa(ba)*bb { aabb, aababb, aabababb, ... } (a + a) {a} (a + b) {a, b} (a + b)2 (a + b)(a + b) == {aa, ab, ba, bb} (a + b + c) {a, b, c} (a + b)* {λ, a, b, aa, bb, ab, ba, aaa, bbb, aab, bba, ….} (abc) {abc} (λ + a) bc {bc, abc} ab* {a, ab, abb, abbb, …} (ab)* {λ, ab, abab, ababab, …} a + b* {a, λ, b, bb, bbb, …} a (a + b)* {a, aa, ab, aaa, abb, aba, abaa, … } (a + b)* a (a + b)* {a, aaa, aab, baa, bab, …} (a + λ)* (a)* = {λ, a, aa, aaa, ….} x* (a + b) + (a + b) x* (a + b) x* y + y x* y (x + λ)x* x* (x + λ) = x* (x + λ)( x + λ)* (x + λ) x* Theory of Computation 8 Mustansiriya University – college of sciences – computer science department – second class start with a a (a + b)* end with b (a + b)* b start with a and end with b start with a or b not start with b contains exactly 2 a's (b)* a (b)* a (b)* contains at least 2 a's (a + b)* a (a + b)* a (a + b)* contains exactly 2 a's or 2 b's [(b)* a (b)* a (b)*] + [(a)* b (a)* b (a)*)] contains even no of a [ (b)* a (b)* a (b)* ]* not start with a and not contain b with even length of a (aa)+ Strings containing 101 Even number of 0’s and contains 101 Even number of 0’s or contains 101 Every one has at least two zeros that follow it Second symbol not a one End with 00 or 01 Exercise Ex. 1: Find a regular expression over the alphabet { a, b } that contain exactly three a's. Ex. 2: Find a regular expression over the alphabet { a, b } that end with ab. Ex. 3: Find a regular expression over the alphabet { a, b } that has length of 3. Ex. 4: Find a regular expression over the alphabet { a, b } that contain exactly two successive a's. Ex. 5: Find the output (words) for the following regular expressions. (λ)* (x)* + (λ) aa* b bba*a (a + b)* ba (0+1)* 00 (0+1)* (11 + 0)* (0+11)* 01* + (00+101)* (a+b)* abb+ (((01+10)* 11)* 00)* Theory of Computation 9 Mustansiriya University – college of sciences – computer science department – second class Finite Automata  


!"

#
$%&
'(
)$*
 
+
,-(
. 
/0
 is a device consisting of a tape and a control circuit which satisfy the following conditions: 1. The tape start from left end and extends to the right without an end. 2. The tape is divide into squares in each a symbol. 3. The tape has a read only head. 4. The head moves to the right one square every time it reads a symbol. It never moves to the left. When it sees no symbol, it stops and the automata terminates its operation. 5. There is a control determines the state of the automaton and also controls the movement of the head. A DFA represents a finite state machine that recognizes a RE. For example, the following FA: recognize (accept) string ab A finite automaton consists of a finite set of states, a set of transitions (moves), one start state, and a set of final states (accepting states). In addition, a DFA has a unique transition for every state combination. it is a set of states, and its “control” moves from state to state in response to external “inputs” . A finite automaton, FA, provides the simplest model of a computing device. It has a central processor of finite capacity and it is based on the concept of state. finite state machine is a 5 tuple M = ( , Q , A , T S F, , ) where o Q --set of states = {q0, q1, q2, ….} o A -- set of input symbols ={a,b, …, 0, 1, …} o T --set of transitions or rules o S -- an initial state o F -- the final state -- could be more than one final state Input Yes No Theory of Computation 10 Mustansiriya University – college of sciences – computer science department – second class Designing (drawing) FA State with numbers or any name Start - or small arrow Final + or double circle Transition (only one input or symbol on the edge) a,b allowed means (a or b) loop Example: Q = { 0, 1, 2 }, A= { a, b }, F = { 1 }, the initial state is 0 and T is shown in the following table. Transition diagram: TG has many inputs on the edge ab FA has only one input on the edge a Deterministic Finite Automata DFA and Non Deterministic Finite Automata NFA DFA: different input from state to different states NFA: one input from state to different states State (q) Input (a) Input (b) 0 1 2 1 2 2 2 2 2 Theory of Computation 11 Mustansiriya University – college of sciences – computer science department – second class Language accepted by FA String is accepted by a FA if and only if the FA starting at the initial state and ends in an accepting state after reading the string. Examples of languages accepted by FA FA RE a aa a+ = aa* a* a+b (a+b)* a*b Theory of Computation 12 Mustansiriya University – college of sciences – computer science department – second class b(a+b)* (a+b)*b a(a+b)*b (a+b)* b(a+b)* ab(a+b)* a*babb* (aa)*ba contains 3 a's b*ab*ab*ab* Theory of Computation 13 Mustansiriya University – college of sciences – computer science department – second class contains even number of a = (b*ab*ab*)+ a(bba + baa)*bb a Theory of Computation 14 Mustansiriya University – college of sciences – computer science department – second class Converting Regular Expression into a Finite Automata RE FA a aa a+ = aa* NFA a* a+b (a+b)* a*b b(a+b)* NFA Theory of Computation 15 Mustansiriya University – college of sciences – computer science department – second class (a+b)*b NFA a(a+b)*b NFA (a+b)* b(a+b)* NFA ab(a+b)* NFA a*babb* NFA (aa)*ba contains 3 a's b*ab*ab*ab* Theory of Computation 16 Mustansiriya University – college of sciences – computer science department – second class contains even number of a = (b*ab*ab*)+ dividable by 3 all bit strings that begin with 0 and end with 1 all bit strings whose number of 0's is a multiple of 5 all bit strings with more 1's than 0's all bit strings with no consecutive 1's Theory of Computation 17 Mustansiriya University – college of sciences – computer science department – second class Converting NFA into DFA Three steps : 1- find transition table ,-
123
 2- drawing new design  
4
50 3- remove unreachable states $%6
17
 
)
/
89:
)$;
6 Example : convert the following NDFA into DFA Note: Any state contains final mark it will be final state 3)) remove unreachable states (marked by dashed circle – state q1 and state q3 ) because we can not reach it. --------------------------------------------------------------------------------------------------------------------------------- HW convert the following NFA into DFA state a b q0 q1q2 q0 q1 q2 q3 q2 q2q3 q2 q3 q3 - q1q2 q2q3 q2q3 q2q3 q2q3 q2 Theory of Computation 18 Mustansiriya University – college of sciences – computer science department – second class Finite State Machines with Output (Mealy and Moore Machines) Moore Machines Moore machine M is the 5tuple M = (Q, A, O, T, F, s) where Q is a finite set of states A is the finite input alphabet O is the finite output alphabet T is the transition function F is the output function Q
A in addition to the start state or the initial state A Moore machine is very similar to a Finite Automaton (FA), with a few key differences: • It has no final states. • It does not accept or reject input, instead, it generates output from input. • Moore machines cannot have nondeterministic states. Every input gives output not if word belongs to the machine or language like FA In each state we stop we print out what inside that state (it's content) so the output will be more than input by one because we start with start state and print out it's content before we trace the input string Input string aaababbaabb State q0q1q2q2q3q1q0q0q1q2q3q0 Output 010 this machine gives 1 after each aab aabaabaaababaab so we use Moore machine as a string recognizer to give us a mark (1) after each substring so we design a machine put 0 in all states except the one after the one represent end of substring aba The output of the machine contains 1 for each occurrence of the substring aab found in the input string. H.W. Construct a Moore machine that outputs a binary string that contains a 1 for every double letter substring in an input string composed of a’s and b’s. For example if abba is the input string 0010 is the corresponding output. This machine might be considered as a "counting" machine Theory of Computation 19 Mustansiriya University – college of sciences – computer science department – second class Input = 0010 Output=11010 Mealy machines Moore machine M is a 5 tuple M = (Q, A, O, T, F ,s) where Q is a finite set of states A is the finite input alphabet O is the finite output alphabet T is the transition function F is the output function Q
A in addition to the start state or the initial state output on edge same input to output aaabb 01110 Mealy machines are finite-state machines that act as transducers or translators, taking a string on an input alphabet and producing a string of equal length on an output alphabet. Mealy machine does not accept or reject an input string, The machine represented in below, outputs an E if the number of 1s read so far is even and an O if it is odd; for example, the translation of is OEOOOEEO. A Mealy machine that outputs E if the number of 1 is even O if the number of 1 is odd Binary inverter There are no accept states in a Mealy machine because it is not a language recogniser, it is an output producer. Its output will be the same length as its input. The following Mealy machine takes the one's complement of its binary input. In other words, it flips each digit from a 0 to a 1 or from a 1 to a 0. Theory of Computation 20 Mustansiriya University – college of sciences – computer science department – second class Binary Incrementer One thing you will notice is the numbering of the states. Usually, if there are 3 states, we number them 00, 01, and 10. - the input bit string is a binary number fed in backward - The output string will be the binary number that is one greater and that is generated right to left. - The machine will have 3 states: start, carry and no-carry. The carry state represents the overflow when two bits of 1’s are added, we print a 0 and we carry a 1. Let the input string be 1011 (binary representation of 11). • The string is fed into the machine as 1101 (backwards). • The output will be 0011, which when reversed is 1100 and is the binary representation of 12. • In Mealy machine, output length = input length. Hence, if input were 1111, then output would be 0000 (overflow situation). Homework: Construct a Mealy machine that takes a string of a’s and b’s as input and outputs a binary string with a 1 at the position of every second double letter. For example, for ababbaab the machine produces and for the input bbb the output string 011 is produced. Theory of Computation 21 Mustansiriya University – college of sciences – computer science department – second class Kleene's Theorem Any language that can be defined by: Regular expression/ Finite automata/ Transition graph Can be defined by all three methods. Proof There are three parts of our proof : Part1: every language that can be defined by a FA == can be defined by a TG. Part2: every language that can be defined by a TG == can be defined by a RE. Part3: every language that can be defined by a RE == can be defined by a FA. proof of part1 Every FA is itself a TG. Therefore, any language that has been defined by a FA has already been defined by a TG. proof of part2 The proof of this part will be by constructive algorithm. This means that we present a procedure that starts out with a TG and ends up with a RE that defines the same language. If we have many start states = become only one becomes If we have many final states = become only one becomes we are now going to build the RE that defines the same language as TG reduce the number of edges or states in each time Theory of Computation 22 Mustansiriya University – college of sciences – computer science department – second class becomes becomes becomes becomes becomes special case : becomes our goal: unique start state and unique final state. Theory of Computation 23 Mustansiriya University – college of sciences – computer science department – second class Example Find the RE that defines the same language accepted by the following TG using Kleenes theorem. RE=(aa+bb)(a+b)*(aa+bb) Theory of Computation 24 Mustansiriya University – college of sciences – computer science department – second class Example Find the RE that defines the same language accepted by the following TG using Kleenes theorem. RE= [(aa+bb)+(ab+ba)(aa+bb)*(ab+ba)]* Theory of Computation 25 Mustansiriya University – college of sciences – computer science department – second class proof of part3 Rule1: there is a FA that accepts any particular letter of the alphabet. There is an FA that accepts only the word . FA accepts only FA accepts only a FA accepts a+b Rule2: if there is a FA called FA1, that accepts the language defined by the regular expression r1 and there is a FA called FA2, that accepts the language defined by the regular expression r2, then there is a FA calledFA3 that accepts language defined by the regular expression (r1+r2). Example We have FA1 accepts all words with a double a in them, and FA2 accepts all words ending in b. we need to build FA3 that accepts all words that have double a or that end in b. FA1 FA2 FA3 Z1 = x1 or y1 Z2 = x2 or y1 Z3 = x1 or y2 Z4 = x3 or y1 Z5 = x3 or y2 a b -x1 X2 X1 X2 X3 X1 +x3 X3 X3 a b -y1 Y1 Y2 +y2 Y1 Y2 a b Z1 Z2 Z3 Z2 Z4 Z3 Z3 Z2 Z3 Z4 Z4 Z5 Z5 Z4 Z5 Theory of Computation 26 Mustansiriya University – college of sciences – computer science department – second class Example z1=x1 or y1 z2=x2 or y3 z3=x1 or y2 z4=x3 or y1 z5=x1 or y4 z6=x2 or y4 z7=x3 or y3 z8=x3 or y2 z9=x2 or y2 z10=x1 or y3 z11=x3 or y4 z12=x2 or y1 a b -x1 X2 X1 x2 X3 X1 +x3 X3 X3 a b -+y1 Y3 Y2 Y2 Y4 Y1 Y3 Y1 Y4 Y4 Y2 Y3 a b -+z1 z2 z3 z2 Z4 z5 z3 Z6 z1 +z4 Z7 Z8 Z5 Z9 Z10 Z6 Z8 Z10 +Z7 Z4 Z11 Z8 Z11 Z4 Z9 Z11 Z1 Z10 Z12 Z5 +Z11 Z8 Z7 +Z12 z7 Z3 Theory of Computation 27 Mustansiriya University – college of sciences – computer science department – second class HomeWork Let FA1 accepts all words ending in a, and let FA2 accepts all words with an odd number of letters (odd length). Build FA3 that accepts all words with odd length or end in a using Kleene's theorem. FA1 FA2 HomeWork Let FA1 accepts all words ending in a, and let FA2 accepts all words end with b. Build FA3 that accepts FA1+FA2 using Kleene's theorem.