1 vote

Regular expressions cannot be used to express context free grammars. Is there a similar notation that can?

Most domain-specific languages for context-free grammars are some variant of Backus-Naur form (BNF). A number of popular programming languages have BNF modules, like python's ...
  • 175
1 vote

Context free language with valid Pumping Lemma use

The language is indeed context-free. Since it can be defined as $L = \{a^kb^kb^la^l\mid k,l\geqslant 0\}$, the following grammar can generate it: $S \rightarrow XY$ $X\rightarrow AXB\mid \varepsilon$ ...
  • 7,568
1 vote

Minimal-length strings which are substrings of no string in a given CFL

Here is a possible approach. Enumerate lengths in increasing order (length 0, length 1, length). For each length, enumerate all strings in lexicographic order, as follows. Let's take length 4 as ...
  • 145k

Only top scored, non community-wiki answers of a minimum length are eligible