The grammar with production rules
S → aSb | SS | λ generates language L given by
| A. | L = {w ∈ {a, b} * | na(w) = nb(w) and na(v) ≥ nb(v) where v is any prefix of w } |
| B. | L = {w ∈ {a, b} * | na(w) = nb(w) and na(v) ≤ nb(v) where v is any prefix of w } |
| C. | L = {w ∈ {a, b} * | na(w) ≠ nb(w) and na(v) ≥ nb(v) where v is any prefix of w } |
| D. | L = {w ∈ {a, b} * | na(w) ≠ nb(w) and na(v) ≤ nb(v) where v is any prefix of w } |
|
Option: A Explanation : Click on Discuss to view users comments. |
A pushdown automation M,= (Q, Σ, Τ, δ, q0, z, F) is set to be deterministic subject to which of the following condition(s), for every q ∈ Q , a ∈ Σ ∪ { λ} and b ∈ Τ.
(s1) δ(q, a, b) contains at most one element
(s2) if δ(q,λ, b) is not empty then δ(q, c, b) must be empty for every c ∈ Σ
| A. | only s1 |
| B. | only s2 |
| C. | both s1 and s2 |
| D. | neither s1 nor s2 |
|
Option: C Explanation : Click on Discuss to view users comments. |
For every context fiee grammar (G) there exists & algorithm that passes any w ∈ L(G) in number of steps proportional to
| A. | ln|w| |
| B. | |w| |
| C. | |w|2 |
| D. | |w|3 |
|
Option: D Explanation : Click on Discuss to view users comments. Ava said: (2:08pm on Saturday 24th August 2013)
Ans D
Ava said: (2:11pm on Saturday 24th August 2013)
Ans DTheorem: For every context-free grammar there exists an algorithm that parse any w ? L(G) in number of steps proportional to |w|3.
|
Match thefollowing :
a. Context sensitive language i. Deterministic finite automation
b. Regular grammar ii Recursive enumerable
c. Context fiee grammar iii. Recursive language
d. Unrestricted grammar iv. Pushdown automation
Codes
a b c d
| A. | ii i iv iii |
| B. | iii iv i ii |
| C. | iii i iv ii |
| D. | ii iv i iii |
|
Option: C Explanation : Click on Discuss to view users comments. |
The statements S1 and S2 are given as :
S1 - Context-sensitive languages are closed under intersection, concatenation, substitution and inverse homomorphism. .
S2 - Context fiee languages are closed under , complementation, substitution and homomorphism.
| A. | Both S1 and S2 are correct. |
| B. |
S1 is correct and S2 is not correct
|
| C. |
S1 is not correct and S2 is correct
|
| D. | Both S1 'and S2 are not correct |
|
Option: C Explanation : S1 is wrong but S2 is correct because these all are closure properties of CFL. So ans is 'C' Click on Discuss to view users comments. |
