Theory of Computation Test 4

Result

Theory of Computation Test 4

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

Which one of the following is FALSE?

A
There is a unique minimal DFA for every regular language

B
Every NFA can be converted to an equivalent PDA

C
Compliment of every context-free language is recursive

D
Every non-deterministic PDA can be converted to an equivalent deterministic PDA

Solution

(i) TRUE: Set of all regular language has a bijection with set of all minimal DFAs.
(ii) TRUE: Every NFA is a PDA.
(iii). TRUE: Recursive languages are closed under complementation.
(iv). FALSE: Set of all DPDAs is a proper subset of set of all NPDAs.
Question 2
1 / -0

If L(G) is accepted by pushdown automaton and 'S' is a string of length 16 in L(G), how long is a derivative of x in G, if G is Chomsky normal form?

A
31-31

B
314-311

C
317-316

D
319-312

Solution

Chomsky normal form
S → AB
A → a
B → b
Length of string = |S| = 16
Length of the derivate of string x in context free grammar:
2|16| – 1 = 2 × 16 - 1 = 31
Note:
Question say steps needed to generated string of 10 length
e.g. if we need to generate ab (string of length 2)
S → AB
S → aB
S → ab
Number of steps = 2× 2 – 1 = 3
Question 3
1 / -0

If L₁ and L₂ are context free language, then which of the following is always accepted by pushdown automaton (PDA)?

A
\({L_1}\;U\;{L_2}\)

B
\({L_1} - \;{L_2}\)

C
\({L_1} \cap \;{L_2}\)

D
\(\overline {{L_1}\;U\;{L_2}} \)
Solution
- Operation under which context free language is closed: Union, Kleene Closure and Concatenation.
- \({L_1}\;U\;{L_2}\) is context free language ∴ it is accepted by PDA
- Operation under which context free language is not closed: Intersection, complementation, set difference
- \({L_1} - \;{L_2},\) \({L_1} \cap \;{L_2}\) and \(\overline {{L_1}\;U\;{L_2}}\) is not a free language ∴ it is not accepted by PDA.
Question 4
1 / -0

Consider the languages L1, L2 and L3 as given below
L1 = {0^p1^q0^p | p, q ϵ N}
L2 = {0^p1^q | p, q ϵ N and p < q} and
L3 = {0^p1^q0^r | p, q, r ϵ N and p = q = r}
Which of the following statements is NOT TRUE?

A
A DPDA can recognize L1 but not an FA

B
An NPDA can recognize L2 but not an DPDA

C
Neither NPDA nor DPDA can recognize L3

D
None of the above

Solution

TRUE: A DPDA can recognize L1 but not an FA because a stack with finite automata is required to recognize L1.
FALSE: A DPDA can also recognize L2 as one stack with deterministic finite automata can recognize l2.
TRUE: As L3 is CSL a PDA can not recognize it, it will require a LBA.
Question 5
1 / -0

If A is a deterministic context free language and B is also deterministic context language then which of the following will not be accepted by Deterministic Pushdown Automata?
I. A ∪ B
II. A̅
III. A ∩ B
IV. A U B̅

A
Only I and III

B
Only II and IV

C
Only II, III and IV

D
Only I, III and IV
Solution
- Operation under which deterministic context-free language is closed: Complementation, Inverse Homomorphism, Intersection with regular language. CFL is accepted by PDA. Only A̅ is accepted by DPDA
- Operation under which deterministic context-free language is not closed: Union, Intersection, set difference, etc
- Only I, III, and IV are not accepted by DPDA.
NOTE
Deterministic Pushdown Automata → DPDA
Question 6
1 / -0

Consider the following languages:
L₁= aⁿb³^mc⁵ⁿ | n ≥ 1 and m ≥ 1
L₂ = a^2m b^p c²ⁿd^q | m = n and p = q where m, n, p, q ≥ 0
L₃ = aⁿ b^p c^qd^r | p = q = r where n, p, q, r ≥ 0
Which of the following is/are incorrect?
I. L₁ can be accepted by deterministic pushdown automaton.
II. L₂ can be accepted by the non-deterministic pushdown automaton
III. L₃ is a context-free language

A
Only I

B
Only II

C
Only II and III

D
I, II and III
Solution
- If L = an bm ckn where k is constant, then it is a deterministic context-free language ∴ L1= an b3m c5n can be accepted by deterministic pushdown automaton.
- L2 = a2m bp c2n dq | m = n and p = q then L3 = L2 = a2m bp c2m dp it not is a context free language ∴ L2 = a2m bp c2m dp cannot be accepted by non-deterministic pushdown automaton.
- L3 = an bp cn dq | p = q = r then L3 = an bp cp dp it is not a context free grammar.
Question 7
1 / -0

Which of the following is true over {0, 1}?
I. \(L_1={1^{50n}}\;|\;n \ge 1\)
II. \(L_2 ={ {2^{{n}}}\;|\;n \ge3}\)
L₂is written in the binary form where the given language is in decimal.

A
L₁ is accepted FA but not L₂

B
L₂ is accepted by PDA but not by FA

C
L₁ and L₂ can be accepted by PDA as well as FA

D
L₁ and L₂ is not accepted by FA
Solution
- \(L_1={1^{50n}}\;|\;n ≥ 1\) (4n ≥ 1) is in Arithmetic progression ∴ it a regular language and every regular language is accepted by PDA if it is accepted by FA then it is accepted PDA. Regular expression for L₁ (1111...50 times)1*
- \(L_2={2^{n}}\;|\;n ≥ 3\) it is accepted by FA and hence it is accepted by PDA.
- L₂ = {1000(8), 10000(16), 100000 (32), 1000000, ....}. Regular expression for L₂ is 10000*
NOTE:
PDA stands for pushdown automaton
FA stands for finite automaton

User

Question Analysis

Correct -
Wrong -
Skipped -

My Perfomance

Score
-
out of -
Rank
-
out of -

Re-Attempt Weekly Quiz Competition

Theory of Computation Test 4

Result

Theory of Computation Test 4

Score

-

Rank

-

SHARING IS CARING

Question 1

There is a unique minimal DFA for every regular language

Every NFA can be converted to an equivalent PDA

Compliment of every context-free language is recursive

Every non-deterministic PDA can be converted to an equivalent deterministic PDA

Solution

Question 2

31-31

314-311

317-316

319-312

Solution

Question 3

\({L_1}\;U\;{L_2}\)

\({L_1} - \;{L_2}\)

\({L_1} \cap \;{L_2}\)

\(\overline {{L_1}\;U\;{L_2}} \)

Solution

Question 4

A DPDA can recognize L1 but not an FA

An NPDA can recognize L2 but not an DPDA

Neither NPDA nor DPDA can recognize L3

None of the above

Solution

Question 5

Only I and III

Only II and IV

Only II, III and IV

Only I, III and IV

Solution

Question 6

Only I

Only II

Only II and III

I, II and III

Solution

Question 7

L1 is accepted FA but not L2

L2 is accepted by PDA but not by FA

L1 and L2 can be accepted by PDA as well as FA

L1 and L2 is not accepted by FA

Solution

User

Question Analysis

My Perfomance

Score

-

Rank

-

Results Announcement on: coming Monday

Stay Tuned: We’ll update you on your result via email or SMS.

L₁ is accepted FA but not L₂

L₂ is accepted by PDA but not by FA

L₁ and L₂ can be accepted by PDA as well as FA

L₁ and L₂ is not accepted by FA