# 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 '18 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$.
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.