Question
L1 = {a^(n+m) b^n a^m ∣ n,m ≥ 0}
L2 = {a^(n+m) b^(n+m) a^(n+m) ∣ n,m ≥ 0}
Which of the following is correct?
a.
Only L1 is context-free language
b.
Only L2 is context-free language
c.
Both L1 and L2 are context free languages
d.
Both L1 and L2 are not context free languages
Engage with the Community - Add Your Comment
Confused About the Answer? Ask for Details Here.
Know the Explanation? Add it Here.
Q. Consider the following languages: L1 = {a^(n+m) b^n a^m ∣ n,m ≥ 0} L2 = {a^(n+m) b^(n+m) a^(n+m) ∣ n,m ≥ 0} Which of the following is correct?
Similar Questions
Discover Related MCQs
Q. Consider R to be any regular language and L1, L2 be any two context-free languages. Which of the following is correct?
View solution
Q. Consider the following problems:
(i) Whether a finite state automaton halts on all inputs?
(ii) Whether a given context free language is regular?
(iii) Whether a Turing machine computes the product of two numbers?
Which one of the following is correct?
View solution
Q. Which of the following problems is decidable for recursive languages (L)?
View solution
Q. Consider the following grammar G:
S → A ∣ B
A → a ∣ c
B → b ∣ c
where {S, A, B} is the set of non-terminals, {a, b, c,} is the set of terminals.
Which of the following statement(s) is/are correct?
S1: LR(1) can parse all strings that are generated using grammar G.
S2: LL(1) can parse all strings that are generated using grammar G.
View solution
Q. The grammar S → (S) ∣ SS ∣ ϵ is not suitable for predictive parsing because the grammar is
View solution
Q. Two finite state machines are said to be equivalent if they:
View solution
Q. A pushdown automata behaves like a Turing machine when the number of auxiliary memory is:
View solution
Q. Pushdown automata can recognize language generated by ................
View solution
Q. To obtain a string of n Terminals from a given Chomsky normal form grammar, the number of productions to be used is:
View solution
Q. Consider the following two Grammars:
G1 : S → SbS | a
G2 : S → aB | ab, A→GAB | a, B→ABb | b
Which of the following option is correct?
View solution
Q. Context sensitive language can be recognized by a:
View solution
Q. The set A={ 0^n 1^n 2^n | n=1, 2, 3, ......... } is an example of a grammar that is:
View solution
Q. A bottom-up parser generates:
View solution
Q. Consider the following statements:
S1 : There exists no algorithm for deciding if any two Turing machines M1 and M2 accept the same language.
S2 : The problem of determining whether a Turing machine halts on any input is undecidable.
Which of the following options is correct?
View solution
Q. Which of the following regular expressions, each describing a language of binary numbers (MSB to LSB) that represents non-negative decimal values, does not include even values? (Where {+, *} are quantification characters.)
View solution
Q. Which of the following statements is/ are TRUE?
(a) The grammar S → SS a is ambiguous. (Where S is the start symbol)
(b) The grammar S → 0S1 | 01S | ϵ is ambiguous. (The special symbol ϵ represents the empty string) (Where S is the start symbol)
(c) The grammar (Where S is the start symbol)
S → T/U
T → x S y | xy | ϵ
U → yT
generates a language consisting of the string yxxyy.
View solution
Q. Pumping lemma for regular language is generally used for proving:
View solution
Q. Which of the following problems is undecidable?
View solution
Q. Finite state machine can recognize language generated by ....................
View solution
Q. The language L = {a^i b c^i | i ≥ 0} over the alphabet {a, b, c} is:
View solution
Suggested Topics
Are you eager to expand your knowledge beyond Theory of Computation(TOC)? We've curated a selection of related categories that you might find intriguing.
Click on the categories below to discover a wealth of MCQs and enrich your understanding of Computer Science. Happy exploring!
