Q. Which grammar is not regular

View solution

Q. If is a language, and is a symbol, then, the quotient of and, is the set of strings such that is in: is in. Suppose is regular, which of the following statements is true?

View solution

Q. Here is a context-free grammar G: S → AB A → 0A1 | 2 B → 1B | 3A which of the following strings are in L (G)?

View solution

Q. The grammar G: S → SS | a | b is ambiguous. Check all and only the strings that have exactly two leftmost derivations in G

View solution

Q. For the following grammar: S → A | B | 2 A → C0 | D B → C1 | E C → D | E | 3 D → E0 | S E → D1 | S Identify all the unit pairs

View solution

Q. The classes of languages P and NP are closed under certain operations, and not closed under others. Decide whether P and NP are closed under each of the following operations.
1. Union

2. Intersection

3. Intersection with a regular language

4. Kleene closure (star)

5. Homomorphism

View solution

Q. Ndfa and dfa accept same languages

View solution

Q. If the NFA N has n states, then the corresponding DFA D has 2n states

View solution

Q. An NFA is nothing more than a ε-NFA with no ε transitions

View solution

Q. For every DFA, there is a ε-NFA that accepts the same language

View solution

Q. DFAs, NFAs, and ε-NFA s are equivalent

View solution

Q. Consider the languages L1 = and L2 = {a}. Which one of the following represents L1 L2* U L1*

View solution

Q. Given the language L = {ab, aa, baa}, which of the following strings are in L*?
1) abaabaaabaa

2) aaaabaaaa

3) baaaaabaaaab

4) baaaaabaa

View solution

Q. Which of the following are regular sets?
I. { a^n b^2m | n>=0, m>=0}

II. {a^n b^m |n=2m}

III. {a^n b^m | n!= m}

IV {xcy |x,y€{a,b)*}

View solution

Q. Let L1 = {w ∈ {0,1}∗ | w has at least as many occurrences
of (110)’s as (011)’s}.
Let L2 = { ∈ {0,1}∗ | w has at least as many occurrences
of (000)’s as (111)’s}.
Which one of the following is TRUE?

View solution

Q. The length of the shortest string NOT in the language (over Σ = {a, b}) of the following regular expression is _____________
a*b*(ba)*a*

View solution

Q. How many minimum states are required to find whether a string has odd number of 0’s or not

View solution

Q. Consider alphabet ∑ = {0, 1}, the null/empty string λ and the sets of strings X0, X1 and X0.How are X1 and X2 are related ?
X0 = 1 X1

X1 = 0 X1 + 1 X2

X2 = 0 X1 + {λ}

Which one of the following represents the strings in X0?

View solution

Q. Which of the following languages is/are regular?
L1: {wxwR ⎪ w, x ∈ {a, b}* and ⎪w⎪, ⎪x⎪ >0} wR is the reverse of string w

L2: {anbm ⎪m ≠ n and m, n≥0

L3: {apbqcr ⎪ p, q, r ≥ 0}

View solution

Q. The set of all strings over ∑ = {a,b} in which strings consisting a’s and b’s and ending with in bb is

View solution