# Is the set of all Context free languages a Context sensitive Language? ( can we build a LBA that decides whether a given language is CFL or not?)

What i mean is that can we code each CFL ( the same way we code each turing machine in the Universal Turing Machine ) and build a Linear bounded Automata in such a way that for each input ( which is a code of a particular CFL) decides whether this is a context free language ( accept ) or not?

I hope my question makes sense or maybe I'm confused, because i know that set of all regular expressions(regular languages) is a Context sensitive language because we can make a context sensitive grammar for it so i was wondering what can we say about the set of all context free languages?

• You can recognise a string representing a regular expression with a context free grammar.
– rici
Mar 24, 2018 at 14:41

If you consider a grammar $(N, \Sigma, P, S)$ you could actually give a regular expression for the production rules $P$, which pretty much determine the whole grammar: $$r = S \to (\bar{N} + \bar{\Sigma})^\ast (| (\bar{N} + \bar{\Sigma})^\ast)^\ast (, \bar{N} \to (\bar{N} + \bar{\Sigma})^\ast (| (\bar{N} + \bar{\Sigma})^\ast)^\ast)^\ast$$ over the alphabet $N \cup \Sigma \cup \{,, |, \to\}$, where we use the $\bar{N}, \bar{\Sigma}$ as shortcut for $\sum_{A \in N} A$ and $\sum_{a \in \Sigma} a$.

So you could pass the grammar (the "code" of the cfl) to a finite automaton to check whether it is a context-free-grammar.

Basically, you just have to check whether there is only one single non-terminal in front of a $\to$. There is no nesting in contex-free grammars in contrast to regular expressions.

• @rici Did I misunterstood the question? I think OP wants to know whether it is possible to decide whether the encoding of a language (here as grammar) is context-free with an LBA and I stated that it is even possible with a finite automaton. However, one should probably add that there is no way to determine for an arbitrary grammar you cannot determine if its represented language might be context-free. Mar 24, 2018 at 14:48
• no, i think you understood it fine; my comment was not well thought through. But there is no real difference with regular languages, because a regular language can be described by a left-linear CFG, and the left-linearity constraint is itself regular.
– rici
Mar 24, 2018 at 15:04
• Also: as you say, you construct a regular expression, which can be recognised by a finite-state automaton; the power of an LBA is not required. A more readable construction produces a CFG, which also can be recognised without the power of an LBA. An LBA is needed to recognise a non-empty CFL.
– rici
Mar 24, 2018 at 15:13