Q. Given the following two grammars :

G1 :     S → AB | aaB

A → a | Aa

B → b

G2: S→ aSbS|bSaS|λ

Which statement is correct ?

View solution

Q. Match the following:

List-I                                                            List-II

a. Chomsky Normal form                       i.  S→ bSS|aS|c

b. Greibach Normal form                        ii.  S→ aSb|ab

c. S-grammar                                           iii. S→ AS|a

                                                                         A→ SA|b

d. |LL grammar                                        iv. S→ aBSB

                                                                         B→ b

Codes:
a       b       c       d

View solution

Q. Given the following two languages :

L1 = {anbn |n≥1} ∪ {a}

L2= {w C wR|we {a,b}*}

Which statement is correct ?

View solution

Q. The solution of the recurrence relation of T(n) = 3T ( floor (n/4) ) +  n is

View solution

Q. The number of strings of length 4 that are generated by the regular expression (0|?) 1+2* (3|?), where | is an alternation character, {+, *} are quantification characters, and ? is the null string, is:

View solution

Q. Which of the following is FALSE ?

View solution

Q. Consider the languages L1 = ϕ, and L2 = {1}. Which one of the following represents
L1* U L2* L1* ?

View solution

Q. Given the following statements :
(A) A class of languages that is closed under union and complementation has to be closed under intersection.
(B) A class of languages that is closed under union and intersection has to be closed under complementation.
Which of the following options is correct?

View solution

Q. Given the following two languages:

L1 = {a^nb^n|n≥0, n≠100}
L2 = {w ϵ {a,b,c}*| na(w) = nb(w) = nc(w)}

Which of the following options is correct?

View solution

Q. Given the following two statements:

A. L = {w|na(w) = nb(w)} is deterministic context free language, but not linear.
B. L = {an bn} U {an b2n} is linear, but not deterministic context free language.

Which of the following options is correct?

View solution

Q. Which of the following pairs have different expressive power?

View solution

Q. Which of the following statements is false?

View solution

Q. Let C be a binary linear code with minimum distance 2t + 1 then it can correct upto ............bits of error.

View solution

Q. From the given data below:

a b b a a b b a a b

which one of the following is not a word in the dictionary created by LZ-coding (the initial words are a, b)?

View solution

Q. The number of strings of length 4 that are generated by the regular expression (0+1+|2+3+)*, where | is an alternation character and {+, *} are quantification characters, is:

View solution

Q. Which of the following is FALSE ?

View solution

Q. The regular grammar for the language L = {a^nb^m | n + m is even} is given by

(A) S → S1 | S2
S1 → a S1 | A1
A1 → b A1 | λ
S2 → aaS2 | A2
A2 → b A2 | λ
(B) S → S1 | S2
S1 → a S1 | a A1
S2 → aa S2 | A2
A1 → bA1 | λ
A2 → bA2 | λ
(C) S → S1 | S2
S1 → aaa S1 | aA1
S2 → aaS2 | A2
A1 → bA1 | λ
A2 → bA2 | λ
(D) S → S1 | S2
S1 → aa S1 | A1
S2 → aaS2 | aA2
A1 → bbA1 | λ
A2 → bbA2 | b

View solution

Q. Let Σ = {a, b} and language L = {aa, bb}. Then, the complement of L is

View solution

Q. Consider the following identities for regular expressions :

(a) (r + s)* = (s + r)*
(b) (r*)* = r*
(c) (r* s*)* = (r + s)*

Which of the above identities are true ?

View solution

Q. Given the following two languages:

L1 = {uww^Rn | u, v, w ϵ {a, b}+}
L2 = {uwwR^n | u, v, w ϵ {a, b}+, |u| ≥ |v|}

Which of the following is correct ?

View solution