Theory of Computation Test 1

Result

Theory of Computation Test 1

Score
-
out of -
Rank
-
out of -

TIME Taken - -

SHARING IS CARING

If our Website helped you a little, then kindly spread our voice using Social Networks. Spread our word to your readers, friends, teachers, students & all those close ones who deserve to know what you know now.

Weekly Quiz Competition

Question 1
1 / -0

The number of paths exists for valid string x accepted by Deterministic Finite Automata (DFA) if x runs on DFA is _____.

A
0

B
≥ 1

C
≤ 1

D
1

Solution

There exists unique path for a particular string accepted by DFA which ends in final state.
There exists unique path for a particular string not accepted by DFA which ends in non-final state
Question 2
1 / -0

Which of the following is true?

A
Melay and Moore machine are language acceptors.

B
Finite State automata is language translator

C
NPDA is more powerful than DPDA

D
Melay machine is more powerful than Moore machine.
Solution
Option 1:
- Mealy and Moore machines are finite state transducer (fst).
- Finite accepter play a central role in the study of formal language but in other areas such as digital design, transducers are more important.
- An fst has a finite set Q of internal states and operates in a discrete time frame with translation from one state to another made in the interval between two instances t_n and t_{n + 1}
Option 2:
- Finite state automata are a machine that accepts some input.
- It accepts the regular languages. Finite state machines are not language translators.
Option 3:
DPDA (deterministic push down automata) accepts the deterministic context free languages and NPDA stands for non-deterministic push down automata.
L = pⁿqⁿr^m ∪ p^mqⁿrⁿ |m, n > 0
Language L is not accepted by deterministic pushdown automaton (DPDA) but it is accepted by Non-deterministic pushdown automaton.
That’s why NPDA is more powerful than DPDA.
Option 4:
Mealy and Moore machines are finite state machines that accepts the same language. Both machines have same power.
Important Points:
Every language accepted by DPDA is accepted by NPDA but vice versa is not true.
Question 3
1 / -0

If a minimum state DFA accepting the language L = {x| x ϵ {a, b} *, the number of a’s and b’s in x are divisible by 9 and 15 respectively then the number of states in DFA is?

A
135-135

B
1354-1351

C
1357-1356

D
1359-1352

Solution

In L, a’s in the string x should be divisible by 9 (N(a) % 9 = 0), and the number of b’s in the string x should be divisible by (N(b) % 15 = 0).
∴ (9 × 15) = 135 states will be needed to minimum DFA accepting the given language
Important Points:
In the case of the same symbol, LCM is taken but in case of different symbols, the product is taken.