CS402 Midterm Subjective with References by Moaaz

Solved Subjective · From Midterm Papers · Dec 07,2012 · PSMD01

Q. Point of Kleen Theory.

Answer: (Page 25)

1. If a language can be accepted by an FA then it can be accepted by a TG as well.
2. If a language can be accepted by a TG then it can be expressed by an RE as well.
3. If a language can be expressed by a RE then it can be accepted by an FA as well.

Q. Difference and common between NFA & DFA

Difference

1-In FA Finite number of states, having one initial and some (maybe none) final states. While in NFA Finite many states with one initial and some final state. 2-In FA for each state and for each input letter there is a transition showing how to move from one state to another while in NFA there may be more than one transition for certain letters and there may not be any transition for certain letters. 3-In FA  is valid while in NFA  is not valid.

Common

Finite set of input letters,

Q1. What is the function of mealy machine?

Answer: (Page 60) 1’s complementing and incrementing machines which are basically Mealy machines are very much helpful in computing. The incrementing machine helps in building a machine that can perform the addition of binary numbers.

Q2. Write the first step to convert GTG to FA?

Answer: (Page 26) Step 1 If a TG has more than one start states, and then introduces a new start state connecting the new state to the old start states by the transitions labeled by Λ and make the old start states the non-start states.

Q3. Explain with example that how in GTG's we directly join the initial state with the final state?

Answer: (Page 27) Eliminate the middle state and connect the first state with the last by a single transition (include the possibility of circuit as well) labeled by the RE which is the concatenation of corresponding two REs in the existing sequence.

Q1. Check the given statements or correct or not if not then correct it.

1. String in regular language can not be infinite True
2. Concatenation of finite letters from alphabets called sigma False
3. There cannot be more than one FA,s for same language. False

Q2. What is the difference between the strings and the words of a language?

Answer: (Page 3) Concatenation of finite number of letters from the alphabet is called a string. Words are strings belonging to some language.

Q3. Is there any difference in PALINDROME and reverse of palindrome explain it?

Answer: (Page 6) PALINDROME is The language and words of PALINDROME are called reverse of palindromes

Q6. explain Moor Machine?

Answer: (Page 55) A Moore machine consists of the following A finite set of states q0, q1, q2, … where q0 is the initial state. An alphabet of letters Σ An alphabet  ={x,y,z,…} of output characters from which output strings are generated. A transition table that shows for each state and each input letter what state is entered the next. An output table that shows what character is printed by each state as it is entered.

Q. What are the difference & similarities b/w FA & NFA?

Answer: rep

Q.How can we show transition table of NFA to FA?

Answer: (Page 45) there may be more than one transition for a certain letter and there may not be any transition for certain letter, so starting from the initial state corresponding to the initial state of given NFA, the transition table along with new labels of states, of the corresponding FA, can be built introducing an empty state for a letter having no transition at certain state and a state corresponding to the combination of states, for a letter having more than one transitions.

Q.Is Kleen's star & Kleen's closure are different?

Answer: (Page 7) there is no difference between both

Q. What is the difference b/w Mealy & Moore machine?

Moore machines

Safer do use because outputs change at clock edge May take additional logic to decode state into outputs For Moore machine, output is valid after state transition. Output associated with stable present state

Mealy machines

Typically have fewer states React faster to inputs. don’t wait for clock Asynchronous outputs can be dangerous For Mealy machine, output is valid on occurrence of active clock edge. Output associated with transition from present state to next state. Output in Mealy machine occurs one clock period before output in equivalent Moore machine.