Computation Theory 2020-2021

Regular Expression:- The languages accepted by finite automata are easily described bysimple expressions called Regular Expressions.- Let Σ be an alphabet. The regular expressions over Σ and the setsthat they denote are defined recursively as follows1- Ø is a regular expression and denotes the empty set {}.2- ϵ is a regular expression and denotes the set { ϵ }3- For each a in Σ, a is regular expression and denotes the set {a}.4- If r and s are regular expressions denoting the language R and S,respectively then (r s), (rs), and (r*) are regular expressions denotethe sets RυS, RS and R* respectively.

Regular Expression:- In writing regular expressions we can omit many parentheses if weassume that * has higher precedence than concatenation or , andthat concatenation has higher precedence than , for example((0(1*)) 0) may be written 01* 0.We may abbreviate the expression rr* by r .r* {ϵ,r, rr, rrr, rrrr, }r {r, rr, rrr, rrrr, }rr* r(ϵ,r, rr, rrr, rrrr, ) r,rr,rrr,rrrr, r 𝑖𝐿 σ 𝑖 0 𝐿𝑖𝐿 σ 𝑖 1 𝐿𝐿0 ϵ

Language Exampleexample1:Let L1 {10, 1} and L2 {011, 11}L1L2 {10011, 1011, 111}L1 L2 {10, 1, 011, 11}L1* {ϵ, 10, 1, 1010, 11, }L1 {10, 1, 1010, 11, }example2:L1 {01, 0}, L2 {ϵ, 0, 10}L1L2 {01, 010, 0110, 0, 00}L2L1 {01, 0, 001, 00, 1001, 100}L1ϵ L1 {01, 0}L1* {ϵ, 01,0,0101,00,010,001, }

Examples of Regular Expression 00 is a regular expression representing {00}.L {00}q00q10q2FA (0 1) * is a regular expression denotes all strings of 0's and1's.L {ϵ, 0, 1, 00, 11, 01, 10, }0,1q2q0

0* 1* is a regular expression denotes all strings of 0's and 1's0* {ϵ, 0, 00, 000, }1* {ϵ, 1, 11, 111, }L 0* 1* {ϵ ,0, 1, 00, 11, 000, 111, } 0*1*2* is a regular expression denotes the language of any numberof 0's followed by any number of 1's followed by any number of2’s. (0 1)*011 is a regular expression denotes the language of mixedgroup of 0's and 1's ended by 011. ((0 1)* 00 (0 1) * is a regular expression denotes the language ofall string of 0's and 1’s with at least two consecutive 0’s.

Finite Language L that contains all the strings of a's of b's of lengthexactly three L {aaa, aab, aba, abb, bab, bba, bbb,baa}. Thefirst letter of each word in L is either a or b, the second letter ofeach word in L is either is either a or b, the third letter of eachword in L is either a or b so we may write L ((a b)(a b)(a b)). a(a b)*b is a regular expression denotes the language of all wordsthat begin with a and end with b . (a b)*aa(a b)* is a regular expression denotes the language allwords over the alphabet Σ {a,b} with at least two consecutive a's (a b)*abb is a regular expression denotes the language of allstring of a's and b's ending in abb.

The language defined by the regular expression a*b* is the set ofall the string of a's and b's L { ϵ, a, b, aa, bb, ab, aaa, aab, abb,bbb, aaaa, }. Language of expressions a*b* (ab)*Since the language defined by the expression on the right containsthe word abab, which the language defined by the expression onthe left does not. Consider the language T defined over the alphabet Σ {a, b, c} ,T {a, c, ab, cb, abb, cbb, abbb, cbbb, abbbb, cbbbb, abbbbb,cbbbbb, }.All the words in T begin with an a or c and then are followed bysome number of b’s.Symbolical we may write this as T ((a c) b*).

(b ba)* is a regular expression denotes the language of all string ofa's and b's beginning with b and not having two consecutive a’s. (a b)*(aa bb)(a b) * is a regular expression denotes the languageof all words over the alphabet Σ {a,b} with at least two.consecutive a’s or two consecutive b’s The language defined by the regular expression ab*a is the set ofall string of a’s and b's that have at least two letters, that beginand end with a’sb* {ϵ,b,bb,bbb,bbbb, }L {aa, aba, abba, abbba, abbbba, }

Thanks forlistening

Formal Definition of grammarComputation Theory2nd Class/1st SemLecture 6 م وجدان عبد االمير حسن . ا

ComputationTheoryEquivalence of finite automata andregular expression

Equivalence of finite automata and regular expression:Non DeterministicFiniteautomata(NFA)NFA with ϵ-Deterministic FiniteAutomata(DFA)transitionRegular Expression(RE)

TheoremLet r be a regular expression. Then there exists an NFA with ϵ-transitionsthat accepts L(r).Case 0 (zero operation)qfq0q0(b) r Ø(a) r ϵq0a(C) r aqf

Regular Expression:Case 1 (one or more operators)r1r r1 r2q1M1f1ϵϵf0q0ϵq2M2r2f2ϵM1 (Q1, Σ1,𝛿1,q1,f1)M2 (Q2, Σ2,𝛿2,q2,f2) let q0 be a new initial state and f0 anew final stateM (Q1 Q2 {q0,f0}, Σ1 Σ2, 𝛿,q0,f0}

Case 2r r1r2M1q1ϵf1q2M2f2M (Q1 𝑄2, Σ1 Σ2, 𝛿,q1,f2}Case 3r r1*ϵq0ϵq1M1f1ϵM (Q1 {𝑞0, 𝑓𝑜}, Σ 1,𝛿,q0,f0}ϵf0

Case 3r r1 ϵq0ϵq1M1f1M (Q1 {𝑞0, 𝑓𝑜}, Σ1,𝛿,q0,f0}ϵf0

Example1Construct an NFA with ϵ for the following regular expressionRE 01* 1r r1 r2r2 1q11q2r1 01*q30q5q41q6ϵq7ϵq51ϵq6ϵq81*

Example1:Construct an NFA with ϵ for the following regular expression RE 01* 1ϵ0q3q4ϵ1q1q21q5q6ϵr1 01*q8ϵr2 11q1ϵϵq7q2ϵq0qfϵϵq30q4ϵq7ϵ1q5RE 01* 1ϵq6ϵϵq8

Example2Construct an NFA with ϵ for the following regular expressionRE (ba q10

Example3Construct an NFA with ϵ for the following regular expressionRE (01 10) ϵϵq131q14ϵq17ϵ1q15ϵq16ϵq18

Thanks forlistening

Computation Theory2nd Class/1st SemLecture 7 م وجدان عبد االمير حسن . ا

ComputationTheoryFinite Automata with output

Finite Automata with outputOne limitation of the finite automata as we havedefined it is that its output limited to a binarysignal: "accept/don’t accept”. Models in whichthe output is chosen from other alphabet havebeen considered.There are two distinct approaches; the outputmay be associated with the state(called a Mooremachine)or with the transition (called MealyMachine).

Moore machineA Moore machine is a six-tuple(Q,Σ, Δ, δ, λ, 𝑞0)where Q,𝜮, 𝜹and q0 are as in the DFA. 𝜟 is the output alphabet and λis a mapping from Q to Δ giving the output associated witheach state.The output of M in response to input a1a2 an , n 0,isλ (q0) λ (q1) λ (q2) λ (qn),where q0,q1,q2, qn is thesequence of states such that δ(qi-1,ai) qi for 1 i n.Note that any Moore machine gives output λ (q0) inresponse to input Є.

Example:y1y3z1q1z2z1z2q3y2q2z1z2Moore machineQ {q1,q2,q3,q4}𝛥 {y1,y2,y3}𝛴 {z1,z2}q0 q1z2q4y1𝝀 𝒒𝟏 y3𝜆(q2) y1𝜆(q3) y2𝜆(q4) y1z1

Example:y1y3z1q1q2z2z1z2q3z2z1z1q4z2y2y1The behavior of the Moore machine can be expressed in the formof the transition tabley3y1y2y1- q1q2q3q4z1q2q3q2q4z2q4q2q1q3outputinputstate

Example1Draw a transition diagram of a Moore machine to determine the remainder(mod3)For each binary string treated as binary integer.01234567890001101110010111011110001001(0 mod 3) 0(1 mod 3) 1(2 mod 3) 2(3 mod 3) 0(4 mod 3) 1(5 mod 3) 2(6 mod 3) 0(7 mod 3) 1(8 mod 3) 2(9 mod 3) 0011q0002q11Moore machineq201

Mealy machineA Mealy machine is a six-tuple(Q,Σ, Δ, δ, λ, 𝑞0) where all is in theMoore machine, except that λ maps Q * 𝛴 to Δ .That is λ(q,a) gives the output associated with the transitionfrom state q on input a. The output of M in response to inputa1a2a3a4 an is λ(q0,a1), λ(q1,a2), λ(q2,a3) λ(qn-1,an) , whereq0,q1,q2, qn is the sequence of states such that δ(qi-1,ai) qifor 1 i n.Note that this sequence has length n rather than length n 1 asfor the Moore machine and on input Є a Mealy machine givesoutput Є.

Example:Consider the language(0 1)* (00 11) for all strings of 0’s and 1’s whoselast two symbols are the 0p1inputinput0p0p0p00nyn1p1p1p11nnyδ tableλ table

Equivalence of Moore and Mealy machines:Theorem If M1 (Q,Σ, Δ, δ, λ, 𝑞0) is a Moore machine, thenthere is a Mealy machine M2 equivalent to M1.Proof: Let M2 (Q,𝛴, 𝛥, 𝛿, 𝜆 , 𝑞0) and define 𝝀 (q,a) to be𝝀(𝜹(q,a)) for all states q and input symbols a. Then M1 andM2 enter the same sequence of states on the same input,and with each transition M2 emits the output that M1associates with the state entered.

Example1: Convert the following Moore machine to mealy machine.01q010q12q2Moore machine100𝝀 (q,a) 𝝀(𝜹(q,a))1Σ {0,1}Δ {0,1,2}𝜆 (q0,0) 𝜆(𝛿(q0,0)) 𝜆 (q0) 0𝜆 (q0,1) 𝜆(𝛿(q0,1)) 𝜆 (q1) 1𝜆 (q1,0) 𝜆(𝛿(q1,0)) 𝜆 (q2) 2𝜆 (q1,1) 𝜆(𝛿(q1,1)) 𝜆 (q0) 0𝜆 (q2,0) 𝜆(𝛿(q2,0)) 𝜆 (q1) 1𝜆 (q2,1) 𝜆(𝛿(q2,1)) 𝜆 (q2) 20/21/1q1q00/01/0q20/11/2Mealy machine

Equivalence of Moore and Mealy machines:Theorem let M1 (Q,Σ, Δ, δ, λ, 𝑞0) be a Mealy machine, thenthere is a Moore machine M2 equivalent to M1.

Thanks forlistening

Formal Definition of grammarComputation Theory2nd Class/1st SemLecture 8 م وجدان عبد االمير حسن . ا

ComputationTheoryKleene's Theorem

Kleene's theoremAny language that can be defined by1-Regular Expression2-Finite Automata3-Transition GraphPart1:-Every language that can be defined by afinite automata can also be defined by a transitiongraph.Every finite automata is itself a transition graph.therefore, any language that has been defined by afinite automata has already been defined by atransition graph.

Part2:-Every language that can be defined by atransition graph can also be defined by a regularexpression.This means that we present a procedure that starsout with a transition graph and ends with a regularexpression that defined the same language.First want to simply T so that it has only one startbЄq3Єabaaq5q4

Another simplification we can make in TG is that itcan be modified to have a unique final state withoutchanging the language it accepts.bq8aaababbecomesЄaaabaq9q8qfЄq9It should be clear that the addition of these two new statesdoes not affect the language that TG(transition graph)accepts. Any word accepted by old TG is also accepted bythe new TG, and any word rejected by the old TG is alsorejected by the new TG.

Pass operation:- If three states in arrow connected by edges labeled withregular expression, we can eliminate the middleman and go directly fromone outer state to the other by a new edge labeled with a regularexpression that is the concatenation of the two previous labels.r1r3q2q1q3We can replace this withq1r1r3q3r2q1r1q2r3becomesq1r1r2*r3q3q3

Example:-TG which accepts all words that begin and end with �q1q4bbq3Єa baaq0aa bbq2Єq4q1bbq3Є

Example:-TG which accepts all words that begin and end withdouble lettersa bq0aa bbaaq4q1bbЄq3a bq0aaaa bbq1q4bb(aa bb)(a b)*aaq0q4(aa bb)(a b)*bb(aa bb)(a b)*aa (aa bb)(a b)*bbq0q4Re (aa bb)(a b)*aa (aa bb)(a b)*bb (aa bb)(a b)* (aa bb)

homework:-The following TG which accepts all words with aneven number of a’s and even number of b’saa,bbaa,bbab,baq2ab,baWhat is the regular expression of the above diagram ?aa,bbq0aa,bbab,baϵq2ϵab,ba

aa bbq0aa bbab baϵq2ϵab baaa bbq0ϵϵ(ab ba)(aa bb)*(ab ba)

(aa bb) (ab ba)(aa bb)*(ab ba)q0ϵϵ[(aa bb) (ab ba)(aa bb)*(ab ba)]*q0RE [(aa bb) (ab ba)(aa bb)*(ab ba)]*

Part 3:- Every language that can be defined by aregular expression can also be defined by a finiteautomata.If there is an FA called FA1 that accepts the languagedefined by regular expression r1 and there is an FAcalled FA2 that accepts the language defined by theregular expression r2, then there is an FA called FA3that accepts the language defined by regularexpression (r1 r2).

Example:Find FA1 FA2bFA1aax2x1ba,bax3FA2by1abFA1 the machine that accepts only strings with a double a in themFA2 the machine that accepts all words that end in the letter bab-Z1 [x1,y1]z2 [x2,y1]Z3 [x1,y2]Z2 [x2,y1]Z4 [x3,y1]Z3 [x1,y2] Z3 [x1,y2]Z2 [x2,y1]Z3 [x1,y2] Z4 [x3,y1]Z4 [x3,y1]Z5 [x3,y2] Z5 [x3,y2]Z4 [x3,y1]Z5 [x3,y2]az1baabbbz2z3z4abaz5FA1 FA2y2

-If there is an FA called FA1 that accepts thelanguage defined by regular expression r1 and thereis an FA called FA2 that accepts the language definedby the regular expression r2, then there is an FAcalled FA3 that accepts the language defined byregular expression (r1.r2).

Example:Find FA1.FA2baaFA1x2x1ba,bax3y1FA2by2abFA1 the machine that accepts only strings with a double a in themFA2 the machine that accepts all words that end in the letter basolutionb-Z1 [x1]z2 [x2]Z1 [x1]Z2 [x2]Z3 [x3,y1]Z1 [x1]Z3 [x3,y1]Z3 [x3,y1]Z4 [x3,y1,y2]Z3 [x3,y1]Z4 [x3,y1,y2] Z4 [x3,y1,y2]baz1babz2abz3z4aFA1.FA2

Thanks forlistening

Formal Definition of grammarComputation Theory2nd Class/1st SemLecture 9 م وجدان عبد االمير حسن . ا

ComputationTheoryGrammar

The formal definition of GrammarG (V,T,P,S) WhereV is a Finite set of Variable(non-terminal)(represented by upper caseletters)T is a Finite set of terminal (represent by lower case letter)P is a Finite set of productionS is called the start symbol (non-terminal)Example:G ({S,A,B},{a,b},P,S} consist of productionS 𝑨 𝑩A aA aPB bB bS 𝐴 aS 𝐵 bS 𝐴 aA aaS B bB bbS 𝐴 aA aaA aaaS B bB bbB bbbS 𝐴 aA aaA aaaA aaaa S B bB bbB 𝑏𝑏𝑏𝐵 bbbbL(G) { an n 1} υ {bn n 1}

Derivation:- is used to generate(determine)sentence of thegiven language,(and it is sequence of application the rule toproduce the finished string of terminal from S.Notations denotes derivation𝛼 𝛽G: 𝛼 drives 𝛽 by one application of some production*𝛼 𝛽G: 𝛼 drives 𝛽 by zero or more applicationi𝛼 𝛽G: 𝛼 drives 𝛽 by exactly i step

Definition :- The language generated by G [denotedL(G)] is {w w in T* and S *G w} that is, a string is inL(G) if:1) The string consists solely of terminals.2) The string can be derived from S.Example:ConsiderthefollowinggrammarG {{S},{a},P,S} where P consist ofS aS aS aaaSolution:S aS aS aaS aS aaS aaanL(G) { a n 1}

Leftmost and rightmost derivations:If at each step in a derivation a production is applied tothe left most variable, then the derivation is said to beleftmost.Similarity a derivation in which rightmost variable isreplaced at each step is said to be rightmost.Example:Consider the grammar G ({S,A},{a,b},P,S), where Pconsist ofS aAS aA SbA SS bathe word aabbaaLeftmost derivationS aAS aSbAS aabAS aabbaS aabbaaRightmost derivationS aAS aAa aSbAa aSbbaa aabbaa

Derivation Trees:If is useful to display derivations as trees. Thesepictures, called derivation(or generation orproduction or syntax)trees.Leaf: a vertex which has no sons, usually representa terminal.Interior vertex: a vertex which has one or moresons usually 𝑉.Yield of the derivation tree: if we read the labelof the leaves from left to right, we have asentential form, we call this string the yield.

Example:Consider the grammar G ({S,A},{a,b},P,S}, where P consist ofS aAS aA SbA SS baDraw the derivation tree of the string(aabbaa)S aAS aSbAS aabAS aabbaS aabbaaSaRoot(non terminal)SASabaAba

Example:Consider the grammar G ({E},{id,(,),*, },P,E}, where P consist ofE E E E*E (E) idDraw the derivation tree of the string( (id id)*id )E E*E (E)*E (E E)*E (id E)*E (id id)*E (id id)*idE Root(non terminal)E*(E)E EididEidterminal

Thanks forlistening

Formal Definition of grammarComputation Theory2nd Class/1st SemLecture 10 م وجدان عبد االمير حسن . ا

ComputationTheoryType of Grammar

A phrase Structure Grammar(PSG)Is a 4 tuple (V,T,P,S) WhereV :Finite set of non-terminals.T :is a Finite set of terminals such that V T .P :is a Finite set of production of the form 𝛼 𝛽,where 𝛼 the string on the left hand side of theproduction, is such that 𝜶 (𝑽 𝑻) and 𝛽 thestring on the right hand side of the production, issuch 𝜷 (𝑽 𝑻) *.S V is symbol designed as the start symbol of thegrammar.

Example1:Consider the PSG,G1 ({S,A,B},{a,b},P,S) with productionS 𝐴S 𝐵A aAA aB bBB bThe above productions can be abbreviatedS 𝐴 𝐵A aA a pB bB bL(G1) {an n 1} {bn n 1}

Example2:Consider the PSG,G2 {{S,B,C},{a,b,c},P,S} with productionS 𝑎S𝐵𝐶 𝑎𝐵𝐶CB BCaB abpbB bbbC bccC ccIn this example the left side of the production are not all singlenon terminal.* 𝑎𝑎𝑏𝑏𝑐𝑐S S aBC abC abcS aSBC aaBCBC aabCBC aabBCC aabbCC aabbcC aabbccL(G2) {an bnnc n 1}

Some time ,it ma be that two different grammar Gand G generate the same language L(G) L(G ).In this case the grammars are said to be equivalent .An example of a grammar equivalent to G1 is G3with productionsS aA bB a bA aA apB bB bPSG is also known as unrestricted grammar.

Context Sensitive Grammar(CSG)Suppose a restriction is placed on productions𝜶 𝜷 𝜶 𝜷 that 𝛽 𝑏𝑒 𝑎𝑡 𝑙𝑒𝑎𝑠𝑡 𝑎𝑠 𝑙𝑜𝑛𝑔 𝑎𝑠 𝛼 .Then the resulting grammar is called ContextSensitive grammar(CSG)and the language a ContextSensitive language(CSL).The term “Context-Sensitive” comes from a normalform for these grammar, where each production is ofthe form 𝛼1𝐴𝛼2 𝛼1B𝛼2, with B 𝜖, they permitreplacement of variable A by string B only in the"context"𝛼1𝛼2.

Example:Consider the CSG,G ({S,B},{x,y,z},P,S} with productionS 𝐁𝐲𝐳B x xBcpcy yccz yzz* xxxyyyzzzS S Byz xyzS Byz xBcyz xxcyz xxycz xxyyzzS Byz xBcyz xxBccyz xxxccyz xxxcycz xxxyccz xxxycyzz xxxyyczz xxxyyyzzzL(G) {xn yn zn n 1}

Context Free Grammar(CFG)A limiting to the left-hand sides of each production𝛼 𝛽 in a CSG to be a single nonterminal A B where A 𝑽 𝒂𝒏𝒅 𝑩 𝑽 𝑻 .Example1: Consider a grammar G ({S},{a,b},P,S)and Pis the following setS aSb ab pS abS aSb aabbS aSb aaSbb aaabbbS aSb aaSbb aaaSbbb aaaabbbbL(G) {an bn n 1}

Example2: Consider a grammar G ({S},{a,b},P,S)and Pis the following setS aSb 𝝐 𝑷S 𝜖S aSb abS aSb aaSbb aabbS aSb aaSbb aaaSbbb aaabbbS aSb aaSbb aaaSbbb aaaaSbbbb aaaabbbbL(G) {an bn n 0}

Example3: Consider a grammar G ({S},{a,b},P,S)and Pis the following setS aB bAA aS a bAA PB bS b aBB* abbaS S aB abS abbA abba* bababaS S bA baS babA babaS bababA bababa* baabbaS S bA baS baaB baabS baabbA baabba The language L(G) is the set of all words in Tconsisting of equal number of a’s and b’s.

Example 4: Consider a grammarG ({S,A},{a,b,c,d},P,S)and P is the following setS aSd aAd pA bAc bcS aSd aaAdd aabcddS aSd aaAdd aabAcaa aabb

In computer science we find many examples of finite state systems:-1- Switching circuit, such as the control unit of a computer. . Theory Finite State System Non Deterministic Finite Automata (NFA) Non Deterministic Finite Automaton (NFA): . Let L be a set accepted by a non deterministic finite automata. Then there exists