multiple choice questions Given a context-free language there is a linear gramma
ID: 3762617 • Letter: M
Question
multiple choice questions
Given a context-free language there is a linear grammar that generates it. *
always
sometimes
never
The family of context-free languages is closed under all of the following EXCEPT: *
union
concatenation
complementation
star closure
If L1 is a context-free language and L2 is a regular language, then L1 L2 is context-free. *
always
sometimes
never
If G = ( V, T, S, P ) is a context-free grammar, there is an algorithm for deciding whether or not L(G) is empty. *
always
sometimes
never
The argument in the pumping lemma for context-free languages is based on the fact that in the derivation of any string of length m, we must have the repetition of: *
one terminal in the grammar
one nonterminal (variable) in the grammar
the start symbol of the grammar
one state in a pda that accepts the language
The language, L = { w : (number of a's in w) = (number of b's in w) } is: *
a regular language
a linear context-free language
a context-free language, but not linear
none of the above
If G is a grammar with no -productions, no unit-productions and no useless symbols, and if the dependency graph for its variables has a cycle, then we know: *
The language generated by the grammar is context-free.
The language generated by the grammar is NOT context-free.
The language is infinite.
None of the above
If L1 and L2 are unambiguous context-free languages, then L1 L2 is an unambiguous conext-free language. *
always
sometimes
never
The family of linear languages is closed under: *
union
concatenation
intersection
none of the above
If L1 is linear and L2 is regular, then L1L2 is a linear language. *
always
sometimes
never
Explanation / Answer
Therefore, the correct option is “sometimes”.
Therefore, the correct option is “Complementation”.
Therefore, the correct option is “Always”.
Therefore, the correct option is “sometimes”.
Therefore, the correct option is “one terminal in the grammar”.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.