Toc 2 marks - 2 mark question answer PDF

Preview

Summary

2 mark question answer...

Description

PACol l egeofEngi neer i ngandTechnol ogy Depar t mentofComput erSci enc eandEngi neer i ng

UNIT – I PART-A 1.

2.

Define hypothesis. The formal proof can be using deductive proof and inductive proof. The deductive proof consists of sequence of statements given with logical reasoning in order to prove the first or initial statement. The initial statement is called hypothesis. What is inductive proof. It is a recursive kind of proof which consists of sequence of parameterized statements that use the statement itself with lower values of its parameter.

3.

List any 4 ways of proving the theorem. Proof about sets, Proofs by Contradiction, Proofs by Counter example and Inductive Proofs.

4.

Define Set, Infinite and Finite Set.

5.

6.

Set is Collection of various objects. These objects are called the elements of the set. Eg : A = { a, e, i, o, u } Infinite Set is a collection of all elements which are infinite in number. Eg: A = { a | a is always even number } Finite Set is a collection of finite number of elements. Eg : A = { a, e, i, o, u } Give some examples for additional forms of proof. 1.Proofs about sets 2.Proofs by contradiction 3.Proofs by counter examples Prove 1+2+3+………………+n= n(n+1)/2 using induction method. Consider the two step approach for a proof by method of induction 1. Basis of induction : Let n = 1 then LHS = 1 and RHS = 1 + 1 / 2 = 1 Hence LHS = RHS. 2. Induction hypothesis : To prove 1 + 2 + 3 …… + n = n ( n + 1 ) / 2 + ( n + 1 ) Consider n = n + 1 then 1 + 2 + 3 ……+ n + ( n + 1 ) = n ( n + 1 ) / 2 + ( n + 1 ) = n2 + 3n + 2 / 2 =(n+1)(n+2)/2 Thus it is proved that 1 + 2 + 3 …… + n= n ( n+ 1 ) / 2

7.

Write down the operations on set. i ) A U B is Union Operation If A = { 1, 2, 3 } B = { 1, 2, 4 } then A U B = { 1, 2, 3, 4 } i.e. combination of both the sets.

PACol l egeofEngi neer i ngandTechnol ogy Depar t me ntofComput erSci enc eandEngi neer i ng

8.

9.

ii) A ∩ B is Intersection operation If A = { 1, 2, 3 } B = { 1, 2, 4 } then A U B = { 2, 3 } i.e. Collection of common elements from both the sets. iii) A – B is the difference operation If A = { 1, 2, 3 } B = { 1, 2, 4 } then A U B ={1} i.e. elements which are there in set A but not in B. Write applications of Automata Theory. 1. It is base for the formal languages and these formal languages are useful of the programming languages. 2. It plays an important role in complier design. 3. To prove the correctness of the program automata theory is used. 4. In switching theory and design and analysis of digital circuits automata theory is applied. 5. It deals with the design finite state machines. Define Finite Automation A finite automata is a mathematical model of a system with discrete input and output and a finite number of memory configuration called states and a set of transitions from one state o another state that occurs on input symbols from alphabet Σ. FA is represented as a collection of 5 tuples (Q, Σ, δ, q0, F )

Where Q is finite set of states, which is not empty Σ is input alphabet δ is transition function q0 is start state F is final state Two Types: Deterministic Finite Automata, Non Deterministic Finite Automata 10. Define Deterministic Finite Automation. The finite automata is called DFA if there is only one path for a specific input from current state to next state. A Deterministic finite automata is a collection of 5 tuples (Q, Σ. δ, q0, F ). where Q is a finite set of states, which is non empty. Σ is a input alphabet, indicates input set. δ is a transition function, a function defined for going to next state. QX Σ Q q0 is an initial state (q0 in Q)

PACol l egeofEngi neer i ngandTechnol ogy

11.

Depar t me mput rSci en eandEngi neer i ng 0 ntofC 1o 2e εc  q q Ф Ф q 0 0 1 F is a set of final states. q1 Ф q1 Ф Automation. q2 Define Non-Deterministic Finite * q2 Ф Ф q2 Ф

The finite automata is called NFA when there exists many paths for a specific input from current state to next state. A finite automata is a collection of 5 tuples (Q, Σ. δ, q0, F ). Where Q is a finite set of states, which is non empty. Σ is a input alphabet, indicates input set. δ is a transition function,a function defined for going to next state. QX Σ2Q q0 is an initial state (q0 in Q) F is a set of final states. (F ¿ Q) 12. Define NFA with ε transition. The ε is a character used to indicate null string. i.e the string which is used simply for transition from one state to other state without any input. A Non Deterministic finite automata is a collection of 5 tuples (Q, Σ. δ, q0, F ). Where Q is a finite set of states, which is non empty. Σ is a input alphabet, indicates input set.( ∑U {ϵ}) δ is a transition function. (Qx∑U { ϵ})→2 Q q0 is an initial state (q0 in Q) F is a set of final states. (F ¿ Q) 13. Design FA to check whether given unary number is divisible by three q

1

q

1

q

1

q

0/1 14. Explain the transition function. The mapping function or transition function denoted by δ. Two parameters are passed to this transition function : (i) current state and (ii) input symbol. The transition function returns a state which can be called as next state. Example : δ ( q0, a ) = q1 15. Write short notes on Minimization of DFA? - Reducing the number of states from given FA - First find out which two states are equivalent - For finding the equivalent states we will apply the following rule The two states S1 & S2 are equivalent if and only if both the states are final or non-final states. 16. Explain a transition Table. It is the tabular representation of the FA. For a transition table the transition function is used. Rows represent States Columns represent input symbols Example: 17. Obtain the ε closure of states q0 and q1 in the following NFA with ε transition. 0 1 1 q 0

q 1

q 2

PACol l egeofEngi neer i ngandTechnol ogy Depar t me ntofComput erSci enc eandEngi neer i ng

ε

ε

Solution: ε - CLOSURE {q0} = {q0, q1,q2} ε - CLOSURE {q1} = {q1,q2} ε - CLOSURE {q2} = { q2} 18. Explain a transition diagram. It is a 5-tuple graph used state and edges represent the transitions from one state to another state. Example:

0/1 q 0

0

q 1

19. Differentiate DFA and NFA S DFA 1. deterministic Finite Automata 2. DFA is subset of NFA 3. For given state, on a given input we reach to deterministic and unique state 4. Transition function leads to only one next state. QX ΣQ 5. Constructing DFA for a language is tougher than constructing an NFA 6. Takes more space 7. DFA accepts a string if it reaches an one of the final states after reading all input symbols. 8. There can be more than one DFA recognizing the same language diffe n no.of es. q q q 3 ,1 1 0 1 0 1

2

q 2

NFA Non deterministic Finite Automata Need to convert NFA to DFA For given state, on a given input we reach to more than one state Transition function leads to multiple next states. QX Σ2Q It is easier to design NFA than DFA. It is compact in space NFA accepts a string only when atleast one of the computational branches ends in an accept state. Every NFA has its equivalent DFA recognizing the same language.

q

1

q

0

q

20. What is Alphabet? An alphabet is a finite, nonempty set of symbols. The alphabet of a language is normally denoted by . When more than one alphabets are considered for discussion, then subscripts may be used (e.g.

etc) or sometimes other

PACol l egeofEngi neer i ngandTechnol ogy Depar t me ntofComput erSci enc eandEngi neer i ng

symbol like G may also be introduced. Example:

21. Construct a Finite Automata for the language {0n | n mod 3 = 2, n ≥ 0}

q0 remainder 0 state q1 remainder 1 state q2 remainder 2 state 22. What is - transitions? In an -transition, the tape head doesn't do anything- it doesnot read and it doesnot move. However, the state of the automata can be changed - that is can go to zero, one or more states. This is written formally as implying that the next state could by any one of w/o consuming the next input symbol. 23. What is meant by Automata? An automata is an abstract computing device (or machine). There are different varities of such abstract machines (also called models of computation) which can be defined mathematically. Some of them are as powerful in principle as today's real computers, while the simpler ones are less powerful. ( Some models are considered even more powerful than any real computers as they have infinite memory and are not subject to physical constraints on memory unlike in real computers). Studying simpler machines are still worth as it is easier to introduce some formalisms used in theory. 24. What is String and length of string? Strings or Words over Alphabet :A string or word over an alphabet is a finite sequence of concatenated symbols of . Example : 0110, 11, 001 are three strings over the binary alphabet { 0, 1 } Length of a string : The number of symbols in a string w is called its length, denoted by |w|. Example : | 011 | = 4, |11| = 2, | b | = 1 25. Find the transition function for this NFA

PACol l egeofEngi neer i ngandTechnol ogy Depar t mentofComput erSci enc eandEngi neer i ng

26. Find the ε-closure for the states 1,2,3,4,5,6,7.

27. Language accepted by DFA A DFA accepts a string w=a1 a2 …an, if there is a path in the transition diagram which begins at a start state and ends at an accepting state or final ¿ state with the sequence of labels a 1 a2 …an. i.e L(A)={ w / δ (q0,w) ϵ F } where F is a final state 28. Language accepted by NFA An NFA accepts a string ‘w’ if it is possible to make any sequence of choices of next state while reading the character of ‘w’ and go from start state to any accepting state. If A=(Q,∑, δ ,q0, F) is an NFA, then ¿ (A)={ w / δ (q0,w) ϵ F } where F is a final state 29. Language accepted by ϵ-NFA An ϵ-NFA accepts a string ‘w’ if it is possible to make any sequence of choices of next state while reading the character of ‘w’ and go from start state to any accepting state.

30. 31.

32.

33.

If A=(Q,∑, δ ,q0, F) is an ϵ-NFA, then ¿ (A)={ w / δ (q0,w) ϵ F } where F is a final state What does the word ‘finite’ in the finite automata mean? The word finite represents finite amount of memory. FA can read finite amount of input symbols with limited memory. Define concatenation of languages. The concatenation of two languages L 1& L2 are set of all strings contained by concatenationg any element of L1 with any element of L2. Eg. L1.L2 = L1L2= { xy / xϵL1, yϵL2 } Is it true that the language accepted by any NFA is different from the regular language? Justify your answer. No, any language accepted by DFA, NFA,ε-NFA is called a regular language. For any Finite Automaton we can construct an equivalent regular expression and the language represented by regular expression is regular language. What is structural indution If we have recursive definition, we can prove theorem by using structural induction. Let S(x) be a statement about the structures ‘x’ hat are defined by

PACol l egeofEngi neer i ngandTechnol ogy Depar t mentofComput erSci enc eandEngi neer i ng

some particular recursive definition. 1. Basis: Prove S(x) for the basis structures x. 2. Induction: Take a structure ‘x’, the recursive definition says that it is formed from y1, y2…yn. Assume the statements S(y1), S(y2), …S(yn) and using these prove S(x). 34.

35.

36.

37.

38.

39.

40.

41.

3. Conclusion: Prove the statement S(x) is true for all x. Define Mutual inductions When there ar several independent statements to prove, then we keep the statements separate and prove them all in their own parts of the basis and inductive step. This form of proof is called Mutual inductions. Eg. Automata with on/off switch and pushing the button switch the state between on and off and the switch starts in off state. State regular expression. Let Σ be an alphabet. The regular expressions over Σ and the sets that they denote are defined recursively as follows a. Ø is a regular expression and denotes the empty set. b. ε is a regular expression and denotes the set {ε} c. For each ‘a’ε Σ, ‘a’ is a regular expression and denotes the set {a}. d. If ‘r’ and ‘s’ are regular expressions denoting the languages L1 and L2 respectively then r + s is equivalent to L1 U L2 i.e. union concatenation rs is equivalent to L1L2 How the kleen’s closure or closure of L can be denoted? L* = ¿ i=0 ¿ ∞ Li Example: a*={ε,a,aa,aaa,….} How the positive closure or closure of L can be denoted? L+ = ¿ i=1 ¿ ∞ Li Example: a+={a,aa,aaa,….} Write the regular expression for the language accepting all combinations of a’s. over the set ∑= {a} L = {ε,a,aa,aaa,………………….}\ R = a* Write regular expression for the language accepting the strings which are starting with 1 and ending with 0, over the set ∑ = {0,1}. L = { 10,1100,1010,100010………………….} R= 1(0+1)*0 Show that (0*1*)* = (0+1)* LHS : (0*1*)* = { ε, 0,1,00,11,0011,011,0011110……………….} RHS : (0+1)* = { ε, 0,1,00,11,0011,011,0011110……………….} Hence LHS = RHS is proved Show that (r+s)* ≠ r* + s* LHS : (r+s)*={ ε, r,s,rs,rr,ss,rrrsssr,……………….} RHS : r* + s*= { ε, r,rr,rrr………….}U { ε, s,ss,sss,………….}

PACol l egeofEngi neer i ngandTechnol ogy Depar t mentofComput erSci enc eandEngi neer i ng

42.

43.

44.

45.

46.

= { ε, r,rr,rrr,s,ss,ssss……………..} Hence LHS ≠ RHS is proved What do you mean by homomorphism? A string homomorphism is a function on strings that works by substring a particular sting for each symbol. Eg. h(0) = ab h(1) =  is a homomorphism, where replace all 0’s by ab and replace all 1’s by . Let w = 0011 h(w) = abab State Pumping lemma and its advantages. Let L be a regular set. Then there exists a constant n such that if z is any word in L such that |z| ≥ n then we can write z = uvw such that |uv| ≤ n and |v| ≥ 1 for all i≥0 and uv i w is in L. The n indicates number of states in FA and should not be greater than the number of states. The advantage is used to check whether the given language is regular or not. Describe the following by regular expression. L1 = the set of all strings of 0’s and 1’s ending in 00 L2 = the set of all strings of 0’s and 1’s beginning with 0 and ending with 1 r1 = (0+1)*00 r2 = 0(0+1)*1 Show that (r*)* = r* for a regular expression r LHS = r* = { ε, r,rr,rrr, …………….} (r*)* = { ε, r,rr,rrr, …………….}* (r*)*={ ε, r,rr,rrr, …………….} = r* LHS = RHS Write down the closure properties of regular language The regular languages are closed under 1. Union 2. Intersection 3. Complement 4. Difference 5. Reversal .

6. Closure 7. Concatenation 8. Homomorphism 9. Inverse Homomorphism 47. Write down the relationship between FA and regular expression

PACol l egeofEngi neer i ngandTechnol ogy Depar t mentofComput erSci enc eandEngi neer i ng RE

NFA with ε

DF A

NFA without ε

48. What is pumping lemma? Let L be a regular language. Then there exists a constant n such that for every string w in L such that |w| ≥ n, w = xyz such that i) y≠ε ii) |xy| ≤ n iii) For all i ≥ 0, xyiz ∑ L 49. If L = {a,b} The language starting and ending with ‘a’ of b’s in between, that what is r? r1 = a b*a 50. Give regular expression for L= L1 U L2 over alphabet {a,b} where L1 = all strings of even length L2 = all strings starting with ‘b’ Solution : r = r1 + r2 r = (aa)*(bb)* + b (a+b)* 51. What is dead state? All the non final states which transmit to itselt for all input symbols in ∑, are called Dead state. a/b

q

q = non final state, also dead state. 52. Let ∑ = {0,1} and ∑1 = {0,1,2} with h(0) = 01 and h(1) = 112. Find h(010) and homomorphic image of L = { 00, 010 } Solution : ∑ = {0,1} and ∑1 = {0,1,2} h is defined as : h(0) = 01 and h(1) = 112 h(010) = 0111201 The homomorphic image of L = { 00, 010 }is h(L) = {0101, 0111201} 53. What are operators? If i)

and

are REs over, then so are ii)

iii)

iv)

54. What is precedence rule? Precedence Rule Consider the RE ab + c. The language described by the RE can be thought of either L(a)L(b+c) or L(ab) L(c)as provided by the rules (of languages described by REs) given already. But these two represents two different

PACol l egeofEngi neer i ngandTechnol ogy Depar t mentofComput erSci enc eandEngi neer i ng

languages lending to ambiguity. To remove this ambiguity we can either 1) Use fully parenthesized expression- (cumbersome) or 2) Use a set of precedence rules to evaluate the options of REs in some order. Like other algebras mod in mathematics. For REs, the order of precedence for the operators is as follows: i) The star operator precedes concatenation and concatenation precedes union (+) operator. ii) It is also important to note that concatenation & union (+) operators are associative and union operation is commutative. 55. Limitations of Finite Automata and Non regular Languages. The class of languages recognized by FA s is strictly the regular set. There are certain languages which are non regular i.e. cannot be recognized by any FA Consider the language In order to accept is language, we find that, an automaton seems to need to remember when passing the center point between a's and b's how many a's it has seen so far. Because it would have to compare that with the number of b's to either accept (when the two numbers are same) or reject (when they are not same) the input string. But the number of a's is not limited and may be much larger than the number of states since the string may be arbitrarily long. So, the amount of information the automaton need to remember is unbounded. A finite automaton cannot remember this with only finite memory (i.e. finite number of states). The fact that FA shave finite memory imposes some limitations on the structure of the languages recognized. Inductively, we can say that a language is regular only if in processing any string in this language, the information that has to be remembered at any point is strictly limited. The argument given above to show that

is non regular is informal. We now present a formal method

for showing that certain languages such as

are non regular.

56. What is Moore machine and Mealy machine?

A special case of FA is Moore machine in which the output depends on the state of the machine.An automaton in which the output depends on the transition and current input is called Mealy machine What is Arden’s Theorem? 57. Arden’s theorem helps in checking the equivalence of two regular expressions. Let P and Q be the two regular expressions over the input alphabet _. The regular expression R is given as:R=Q+RP which has a unique solution as R=QP*.

PART-B 1. 2.

Draw transition diagram for recognizing the set of all operators in C language. Explain the extended transition function for NFA, DFA and ε-NFA.

PACol l egeofEngi neer i ngandTechnol ogy Depar t mentofComput erSci enc eandEngi neer i ng

3. 4. 5. 6. 7. 8.

n ( n+1 )(2 n+1) 6 Construct NFA that accepts the set of all stings {a,b} ending with “aba” as substring and construct DFA. A regular language L is accepted by some DFA if and only if L is accepted by some NFA. Equivalence of NFA ε with and without ε.

Prove the following by induction

2

2

2

1 + 2 +… n =

Construct NFA accepting all strings in {a,b}+ with either two consecutive a’s or two consecutive b’s. For the Finite State Machine M given in the following table, test whether the strings 101101, 11111 are accepted...