1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ You can recognise a string representing a regular expression with a context free grammar. $\endgroup$ – rici Mar 24 '18 at 14:41
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – ttnick Mar 24 '18 at 14:48
  • 1
    $\begingroup$ 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. $\endgroup$ – rici Mar 24 '18 at 15:04
  • 1
    $\begingroup$ 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. $\endgroup$ – rici Mar 24 '18 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.