CS402 Final Term Solved Subjective Set 2 by Junaid

Q No 1.How Moore and Mealy machine works in Computer Memory what is their importance in Computing ?

Mealy & Moore Machines work in computing as incrementing machine & 1's complement machine etc. These operations as basic computer operations so these machines are very important. Q No 2.What is sequential circuit ? Sequential Circuit: A sequential circuit contains a memory component. The memory component provides a state input. A flip-flop is often used as a memory component. The state variable indicates the states of the sequential machine, i.e. the status or stage or progress of the whole event. The state of a sequential circuit is indicated by the output of a flip-flop. A single flip-flop can be used to indicate two states (q=0 and q=1). When there are more than two states, additional flip-flops are used. Given n flip-flops, a total of 2n states can be represented. In other words, a sequential machine can be put into a number of different states depending on the particular inputs given. The output is a function of both the Present Inputs and the Present States. In addition to the outputs, the circuit must also generate an update to the memory components so that the state of the machine can also be changed with respect to the new inputs. The update is called the Next State Function and is also a function of the Present Inputs and the Present States. Both the output functions and the Next State Functions are combinational circuits. Z=f(X,St) S=g(X,St) The superscript t indicates the present time period while the superscript (t+1) indicates the next time period. The characteristic of a sequential circuit is completely defined by a state transition diagram that enumerates all possible transitions for every possible input combination. Q No 1.What is the concept of Pumping Lemma I and II and what is the difference between pumping Lemma 1 and pumping Lemma 2 ? In fact PLI & PLII are same (A way to recognize Non Regular language). The only difference is that the conditions in pumping lemma II are more stricter than Pumping Lemma I some language that are difficult to proof Non Regular by Pumping Lemma I are proved Non Regular by pumping Lemma II easily. Further mare in pumping lemma I we have to generate all words to of a language but in Pumping Lemma II we have to generate a single word to prove a language non regular. Explanation: Some languages like PALINDROME that are proved to be regular by first version due to some of their symmetrical words when we pump these words they remain to be the parts of the language like bbabb By pumping lemma 1 Let y = a Now repeating y three times results in bbaaabb That is also a valid word of PALINDROME so by pumping lemma I PALINDROME can not be proved non regular, so there was the need of pumping lemma version version 2. Now consider for the word bbabb if we take N=2 Then by pumping y (let we take it b ) two times results in bbbbabb That word is not in PALINDROME. But if we take N=3 and y = a Then by pumping y two times results in bbaaabb That word is in PALINDROME. So be careful in taking total no of states of the FA and also the repeating factor (y) to prove an infinite language non regular you need to prove only one word that is not part of the language. Q No 2. What is the significance of Pumping Lemma II ? The significance of 2nd version of 'pumping lemma' is that there are some infinite non regular languages like PALINDROME we can built FA that can accept there certain words but if we increase the length of their words that FA don't accept these words so by pumping lemma version I it is very difficult to prove them non regular but with the second version we can prove that a language is Non regular even it's some words may be accepted by some FA's. See page 195 of the book for further example.