adplus-dvertising
frame-decoration

Question

Let P be a regular language and Q be context-free language such that Q ⊆ P. (For example, let P be the language represented by the regular expression p*q* and Q be {p^nq^n|n ∈ N}). Then which of the following is ALWAYS regular?

a.

P ∩ Q

b.

P – Q

c.

∑* – P

d.

∑* – Q

Answer: (c).∑* – P

Engage with the Community - Add Your Comment

Confused About the Answer? Ask for Details Here.

Know the Explanation? Add it Here.

Q. Let P be a regular language and Q be context-free language such that Q ⊆ P. (For example, let P be the language represented by the regular expression p*q* and Q be {p^nq^n|n ∈ N})....

Similar Questions

Discover Related MCQs

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

1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa

Q. Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?

Q. Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?

Q. Which one of the following is FALSE?

Q. Which of the following statements is false?

Q. Which of the following is TRUE?

Q. A minimum state deterministic finite automaton accepting the language L={w | w ε {0,1} *, number of 0s and 1s in w are divisible by 3 and 5, respectively} has

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?

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

a*b*(ba)*a*

Q. Consider the regular language L = (111 + 11111)*. The minimum number of states in any DFA accepting this languages is:

Q. Let Nf and Np denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let Df and Dp denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata, respectively. Which one of the following is TRUE?

Q. The regular expression 0*(10*)* denotes the same set as

Q. The smallest finite automation which accepts the language {x | length of x is divisible by 3} has :

Q. Given an arbitary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least

Q. Consider a DFA over ∑ = {a, b} accepting all strings which have number of a’s divisible by 6 and number of b’s divisible by 8. What is the minimum number of states that the DFA will have?

Q. Let S and T be language over Σ = {a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?

Q. Let L denotes the language generated by the grammar S -> 0S0/00. Which of the following is true?

Q. What can be said about a regular language L over {a} whose minimal finite state automaton has two states?

Q. How many minimum states are required in a DFA to find whether a given binary string has odd number of 0's or not, there can be any number of 1's.

Q. Consider alphabet ∑ = {0, 1}, the null/empty string λ and the sets of strings X0, X1 and X2 generated by the corresponding non-terminals of a regular grammar. X0, X1 and X2 are related as follows:

X0 = 1 X1
X1 = 0 X1 + 1 X2
X2 = 0 X1 + {λ}

Which one of the following choices precisely represents the strings in X0?