Theory of Computation

Question

State True or False.

 

All Linear languages are non-deterministic context free language.

Comments

What’s the confusion here? Definitions you can always see in standard books.

---

What is linear language?

---

https://en.wikipedia.org/wiki/Linear_grammar#:~:text=In%20computer%20science%2C%20a%20linear,generated%20by%20some%20linear%20grammar.

---

@gatecse @Chandrabhan Vishwa 1 

the statement was given true in made easy test series. Which bring me in confusion. 

---

@raja11sep

I think linear language here means the language accepted by Linear Bounded Automata.

---

@gatecse 

What is the meaning of “ I have no human form and many people take my form and contribute here.”

When I generally want to tag you in other question, your name does not highlight. Are you a robot 🤨??

---

can u send test series explanation  

i think this should be true because in category of  linear language only regular language and deterministic contex free  language come and nondeterministic cfl can also come  in this category

---

@GateOverflow04 You cannot give your own definition to a standard term like ‘linear language’. Its definition is given in the Wikipedia page – referring standard resources (Wikipedia is not the best but is still far better than many other online pages) for simple things is one of the first steps in learning. 

Now from the definition of linear grammar, it is always a CFG. So, how can the given statement be False? The question says “non-deterministic” and not “not-deterministic”.

---

@gatecse

non-deterministic context free language belongs to TYPE 2

LINEAR languages  or context sensitive belongs to type 3.

 

correct or wrong???

---

Wrong. Where are you learning such things from?

---

@GateOverflow04  bro linear bounded autometa (csl) and linear language both are different thing..

---

Linear language means language generated by the linear grammar. Now linear grammar can be as powerful as CFG (sometimes) so it can generate some regular language, DCFL, and CFL . so the given statement is true.

Note 1: Every regular grammar is linear grammar but the converse is false.

Note 2: Every Linear grammar is CFG but Converse is not true.

Answer: True.

(CFG - Context Free Grammar)

There are three things you need to know regarding linear languages... 

1. It is the set of all languages created by linear grammars (LHS single variable and rhs atmost one variable i.e T*, T*V, VT* or T*VT*.. 

2. It is a proper superset of Regular languages and a proper subset of CFLs 

3. It is out of syllabus !!!!

@gatecse sir please correct me if I’m wrong.

---

Linear language means language generated by the linear grammar. ✅

Now linear grammar can be as powerful as CFG (sometimes) ❌ Linear grammar is a strict subset of CFG. When we talk about power of a grammar class we are comparing the set of languages that can be generated by that – so power of linear grammar is strictly lower than the power of CFG.

so it can generate some regular language, DCFL, and CFL . ❌ Linear grammar can generate ANY regular language. “Some” is true for DCFL and CFL.

so the given statement is true. ✅

Note 1: Every regular grammar is linear grammar but the converse is false. ✅

Note 2: Every Linear grammar is CFG but Converse is not true. ✅

Answer: True.

(CFG - Context Free Grammar)

There are three things you need to know regarding linear languages...

1. It is the set of all languages created by linear grammars (LHS single variable and rhs atmost one variable i.e T*, T*V, VT* or T*VT*.. Not clear of the given examples.

2. It is a proper superset of Regular languages and a proper subset of CFLs ✅

3. It is out of syllabus !!!! ❌ CFL and regular languages are mentioned in syllabus IIRC and so questions on linear languages can be asked. But GATE questions usually add the definition in question (what is linear language for example) if that is not very basic.

---

@gatecse These are some valuable comments to be bookmarked ❤ Thanks a lot :)

P.s. It would be better if “bookmark comment” would have been a feature. 

---

@gatecse Thanks sir.😍

---

@Abhrajyoti00 exactly.

---

@Abhrajyoti00 By default favorite and even lists are applicable only to questions. But any answer or comment has a unique link and you can always bookmark them in your browser like Chrome or Firefox. 

Answer 1

False,there are some linear  languages which are dcfl,but all linear languages are context free languages.

Comments

While regular languages are deterministic, there exist linear languages that are nondeterministic.