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
Accepted
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 ...
D.W.♦
- 145k
Only top scored, non community-wiki answers of a minimum length are eligible