The set of regular languages $R$ over an alphabet $\Sigma$ can be defined as the smallest set satisfying these 5 axioms:

  • Empty language: $\{\} \in R$
  • Singleton languages: $\forall a \in \Sigma : \{a\} \in R$
  • Closure under union: $\forall A, B \in R : A \cup B \in R$
  • Closure under concatenation: $\forall A, B \in R : A B \in R$
  • Closure under Kleene star: $\forall A \in R: A^* = \bigcup_{i \in \mathbb{N}} A^i = \{\varepsilon\} \cup A \cup A^2 \cup \ldots \in R $

Is there a similar way to define the set of context-free languages in terms of set operations, without invoking context-free grammars or pushdown automata?



Your Answer

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