Tasneem Shafiq

 Formal Languages and Automata Question No.1: Construct a deterministic Finite state machine for each of the following languages 1(a), Strings over the alphabet that have ‘abab’ as a substring Answer: We are considering the initial state will be q0 and the final state will be q4.Now we are required to describe the transition function. That what happens if at q0 we get b, then q0 would not do any transition and wait for an ‘a’ . What happens if at q1 we get one or more a, then q1 will stay there and wait for ‘b’. What happens if at q2 we get b, then finite State Automata has read ab and any other b will destroy substring abab so after that we will be required to start from the beginning that is from q0 in order to wait for a. What happens id at q3 we get a and if we have read aba and waiting for b only then ‘a’ at q3 will destroy the desired substring, however we can considered that ‘a’ as a first ‘a’ of another substring ‘abab’ therefore we are required to go where the first b is waited at q1, While at q4 we are sure that the string holds ‘abab’ so here any sequence of ‘a’ and ‘b’ will be allowed The Finite State Automata is represented by: K = {q0, q1, q2, q3, q4} ∑ = {a,b} s = q0 F = {q4} Transition function given by the following table: States a b ---------------------------- q0q1q0 q1q1q2 q2q3q0 q3q4q1 q4q4q4 Deterministic Finite State Machine 1(b), Strings over the alphabet that have not ‘aa’ nor ‘bb’ as substring According to the question above ,if at q1 a second ‘a ‘comes then the Finite State Automata will jump into q3 while if at q2 a second b comes then the Finite State Automata again gets into q3 and one time at q3 then there is no other option. Hence, q3 is designed not to be considered as a final state. So we are required to construct Final State Automata that will refuse any string initiating with ‘aa’ or ‘bb’. If the string is empty and not containing ‘aa’ and ‘bb’ so the empty string is acceptable, therefore q0 has to be a final state and If the string has only one a or only one b then it is also acceptable, so q1 and q2 have to be final states too. Therefore F = {q0, q1, q2} So the Finite State Automata is represented as K = {q0, q1, q2, q3} ∑ = {a,b} s = q0 F = {q0, q1, q2} The transition function is given in the following table. States a b ---------------------------- q0q1q2 q1q3q2 q2q1q3 q3q3q3 1 C), L= {w; w= abac} We are considering the initial state will be q0 and the final state will be q8.Now we are required to describe the transition function. K = {q0, q1, q2, q3, q4, q5, q6, q7, q8} ∑ = {a,b,c} s = q0 F = {q8} The transition function is given in the following table. States a b c -------------------------------- q0q1q0 q8 q1q1q2 q8 q2q3q0 q8 q3q1q4 q8 q4 q5 q0 q8 q5 q1 q0 q6 q6 q7 q0 q6 q7 q1 q8 q6 q8 q8 q8 q8 Question 2: Yes ,the Deterministic Finite State Machine .We can define minimal Deterministic Finite state machine ,a minimization algorithm that takes as its input a Deterministic Finite state machine where M=(K,∑, and Minimal Deteministic Finite State Machine will comprise a minimal DFSM M’ that is equals to M. it will begin by which divides the state of M into most two equivalence class corresponding to A and K-A ,if M has no accepting states or if all its states are accepting then there will be only non empty equivalence class and we can quit since there is only one state machine that is equivalent to M. Minimal Deterministic executers a series of steps during which it construct the sequence of equivalence e relation , and till .the characteristic of minimal deterministic Finite state machine is that it begins with but it breaks into equivalence classes of whenever it identifies some pair of states that do not behave consistently .Therefore the above deterministic Finite state machine is minimal . Question no 3: (a) Non Deterministic Finite State Machine 3(b) Non Deterministic Finite State Machine Question 7: S T T T W W Finite State Machine M that Accepts L (G) Question 8(a) L= {} Using the Pumping Lemma in order to prove that L= is not regular .We Suppose initially that L is regular then there is a constant n that are satisfying the Pumping Lemma conditions. Consider the string w= then w=xyz where |xy| 0 the string y should be consist of a only so regardless of what segment of the XY part of the string Y ,the pumping y adds to the number of a’s and therefore more number of ‘a’ then ‘b’ hence there is no other way to segment w into xyz so that’s why pumping will not guide to a string that is not in the language. Therefore language is not regular. 8(b) L= { Let us consider a set of string of ‘a’ where p and q are two prime numbers. L= {} where p and q are prime numbers. Here we are claiming that L is not regular. Lets initially suppose that L is regular then there is a constant n that should satisfy the conditions of Pumping Lemma .Consider w=.Let u then u = where 0, 1 and for every m N.this show that i+j+k is a prime number and i+jn+k is also a prime number for every m N for n=i+2j+k+2 we holds I+jn+k=i+j(i+2j+k+2)+k=i+2j+k+j(i+2j+k)=(i+2j+k)(j+1) which no t a prime number as both j+1 and i+2j+k,therefore L is not a regular language. Question 10 S S rule no.1 S rule no.2 S rule no.3 8(a), five strings are: 1. ab 2. aabb 3, aaabbb 4, aaaabbbb 5, aaaaabbbbb 8(b).Derivations of the strings 1. ab S aSb ⇒ ab using rule no.1 and rule no.3 2. aabb S aSb ⇒ aaSbb ⇒ aabb using rule no.1 and rule no.3 3. aaabbb S aSb ⇒ aaaSbbb ⇒ aaabbb using rule no.1 and rule no.3 4. aaaabbbb S aSb ⇒ aaaaSbbbb ⇒ aaaabbbb using rule no.1 and rule no.3 5. aaaaabbbbb S aSb ⇒ aaaaaSbbbbb ⇒ aaaaabbbbb using rule no.1 and rule no.3 8c) The above strings contains a concatenation of two terms in the first string a and b concatenated with each other, while in the second string aa and bb concatenated with each other. In the third string contains concatenation of aaa and bbb took place. In the forth string there is a concatenation of aaaa and bbbb. While, in the fifth string using the rules of context free grammar concatenation of aaaaa and bbbbb occurred.