Automata-Theory-with-activityyyyyyy.pptx

Automsts

1. Central concepts of Automata Automaton – developing a model that takes the input and processes the output. Computability-whether the machine can process the input or not. Complexity- find the optimal solution to the problem. A solution with less complexity

2. BASIC NOTATIONS AND REPRESENTATIONS IN AUTOMATA THEORY Symbol – a,b,c , ……. 0,1,2,……. +,-,#,%, ….. Special character Alphabet Σ (sigma) is a collection of symbols Example 1. Σ ={0,1} is a set of binary numbers 2. Σ ={ a,b,c,d,e,f,g,h,i,j ………z} is a set of lower case letters 3. Σ = {+,-$,%,^,&} is a set of special characters Strings is a collection of symbols over alphabet Σ ={ a,b } in this language the strings are strings = a,b,ab,ba,aa,bb,aaa,bbb ,………. Language L is a set of all strings over alphabet L={ a,b,aa,bb,aaa,bbb,aaaa,bbbb } Example What is a language that accepts strings of length 2 over Σ ={0,1} Solution L2={00,01,10,11} L3={000,001,010,011,100,101,110,111}

3. Kleene star Σ * = universal set, infinite set Σ * = Σ U Σ 1 U Σ 2 U Σ 3 U Σ 4,…. Σ 1= length of string 1 ={ a,b } Σ 2= length of string 2 ={ aa,ab,ba,bb } Σ 0= length of string 0 ={ ε } Σ *={ ε , a,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa,bab,bba,bbb ,………} Kleene closure Σ + = Σ *-{ ε } Σ + = Σ *- Σ Σ + = Σ 1 U Σ 2 U Σ 3 U Σ 4,…. Σ 1= length of string 1 ={ a,b } Σ 2= length of string 2 ={ aa,ab,ba,bb } Σ + ={ a,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa,bab,bba,bbb ,………}

4. Activity What is a language that accepts strings of length 2 over Σ ={ a,b } What is a language that accepts strings of length 0 over Σ ={ a,b } What is a language that accepts strings of length 3 over Σ ={ a,b } What is a language that accepts strings of length 4 over Σ ={ a,b } What is a language that accepts strings of length 5 over Σ ={ a,b } Identify the length of the strings a. x = 1010101000 b. y = 010101000 c. z = 11111010101   What is the concatenation of acc and ba ? What is the concatenation of ba and aa? Let w=aca Find w Find w 1 Find w 2 Find w 3 What is the reverse of aaacdbb ? Let { xy n x |n>1} of a language over Σ ={ x,y }. what are the strings? Let { x n y n x |n>=0} of a language over Σ ={ x,y }. what are the strings? Let { xyx n |n>=0} of a language over Σ ={ x,y }. what are the strings?  sources https://www.youtube.com/watch?v=F3wzZt-dX-8 https://www.youtube.com/watch?v=2-3Ij5_rpKk