Let L1 and L2 be two languages produced by grammars of a certain type. Let L be

Question

Let L1 and L2 be two languages produced by grammars of a certain type. Let L be the language which is the concatenation of L1 and L2. We want to tell for various types of grammars that produce L1 and L2 what type is the concatenation L. Choose the triple (type1, type2, type3) so that when the grammar that produces the language L1 is of type1 and the grammar that produces the language L2 is of type2 , then the grammar that produces the concatenation language L may not be of type3.

Note: A linear grammar is a context-free grammar in which no production

body has more than one occurrence of one variable. For example, A 0B1 or A 001 could be productions of a linear grammar, but A BB or A A0B could not.

A linear language is a language that has at least one linear grammar.

a) (regular,regular,context-free)

b) (linear,regular,linear)

c) (regular, linear,regular)

d) (regular,regular,linear)

Plz explain me to learn more and what is the ans?

Explanation / Answer

We know these are the very well known features of a regular language:
        i)regular languges are closed under concatination
       ii)If L is a linear language and M is a regular language, then the intersection L M is again a linear language; in other words, the linear languages are closed under intersection with regular sets

So
a (regular,regular,context-free) acording to point (i) stated above regular concatinated with regular is a regular lagnguage. And according to Chomsky's Hierarchy every regular language is CFG, so regular concatinated with regular is CFG.
and d (regular,regular,linear) according to point (i) and point (ii) stated above regular concatinated with regular is a regular lagnguage. And according to point(ii) Regular Grammar is a special case of Linear grammar, so (regular,regular,linear) is true.

Now let us consider agrammar rule for linear language: A-> aAb | c
        so A produces ancn
We Cammot use regular expressions to generate Linear Language grammar hence all regular languages are linear; conversely, we have an example of a linear, non-regular language is {anbn},

So the option C stating (regular, linear,regular) is false

So we are left with option B. And it is same for B
let regular language be ck where k is even
and linear language be anbn,

so the concatinated language is ckanbn where k is even
So can you have a linear grammar for this? I dont think so. So B is also false

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.