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?

Improve this question
$\endgroup$
1
  • $\begingroup$ You can recognise a string representing a regular expression with a context free grammar. $\endgroup$
    – rici
    Commented Mar 24, 2018 at 14:41

1 Answer 1

Reset to default
2
$\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 determines 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 shortcuts 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 context-free grammars in contrast to regular expressions.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Mar 24, 2018 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
    Commented Mar 24, 2018 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
    Commented Mar 24, 2018 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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