1
$\begingroup$

General

Given a regular language $L \subset \Sigma^\star$, I wish to generate at least one string not in $L$. (Obviously, this requires that there exists such a string; i.e., that $L \neq \Sigma^\star$. I would be interested in ways to decide this, if any exist.)

(Harder) I wish also to generate at least one string not in $L$, but such that the property $P$ holds. (Again, this requires $\exists w \not\in L : P(w)$ and $\exists w \in \Sigma^\star : P(w)$, but of course one must know $\Sigma,L,P$ to prove any of these.)

A somewhat naïve approach, when we can reliably generate $w : P(w)$, is to do so until $w \not\in L$. For the specific case below, this is not terribly difficult once we can generate strings from a context-free grammar. Is there better?

Specific

After thinking about Balanced braces, my stack-based implementation, and my slight rant about students knowing regular expressions are not sufficient for this problem, I would love to be able to do the following:

Given a regular expression1 that supposedly solves the balanced parentheses problem2, I would like to generate a string in the (context-free) language of balanced parentheses that is rejected by the regular expression.

This would be a nice way to highlight, based on intuition, that some languages are more bigger than others. It would also prove that the given RE is not equivalent to the desired language, though of course it does not constitute a proof that no RE is equivalent.

So, to recap:

  • $L$ is an attempt to recognize all strings in the language of balanced parentheses (doomed to fail);
  • $\Sigma = \{(, )\}$;
  • $P$ is the property that the given string is in the language of balanced parentheses

  1. We can stick with the "proper" definition: concatenation, alternation, and Kleene-star repetition)
  2. Again, stick with just ( and ) for simplicity
| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ Do you want us to answer the general question or the specific one? For the general question: How is $L$ represented? A DFA? a NFA? a regexp? What form does $P$ take, how is it represented, and can you say anything about what class of properties are allowed for $P$ to be? In general if $P$ can be arbitrary the problem is undecidable. $\endgroup$ – D.W. Jan 17 at 22:50
  • $\begingroup$ L’s representation is somewhat arbitrary, though a regex makes the most sense for user-input. I had thought of P as a simple function, but now I see that makes the problem too hard. What about restricting P to « is in this context-free language G »? The general version then opens itself to lots of nifty counter examples for (e.g.) students. Most immediately, though, i would like to eventually program the specific. @D.W. Now that I think about it, I wonder if a QuickCheck-esque solution wouldn’t be quite easy to program. $\endgroup$ – D. Ben Knoble Jan 17 at 22:54
1
$\begingroup$

For your specific question, you are asking to generate a string in $\bar{L} \cap P$. Note that since $L$ is regular, so is $\bar{L}$; and note that $P$ is context-free. It is known that the intersection of a regular and context-free language is context-free. So, you're asking: given a context-free language, how do we generate a word in that language? This is straightforward.

Concretely: you could represent $L$ as a DFA, then take the complement to get a DFA for $\bar{L}$. You could represent $P$ as a context-free grammar. Then, using a product construction, you can obtain a context-free grammar for $\bar{L} \cap P$, remove all non-productive nonterminals, and then generate a random derivation in the grammar (or, if you want to get fancier, you can search for the shortest word in the grammar using a simple algorithm).

The product construction works by replacing each nonterminal $T$ from $P$ with nonterminals of the form ${}_sT_t$, with the intended meaning that $L({}_sT_t)$ is the set of all words $w \in L(T)$ such that if you start the DFA in state $s$ and then feed in $w$, it ends in state $t$. You can figure out how to modify all the rules of the grammar, e.g., $T \to UV$ becomes the collection of rules ${}_sT_u \to {}_sU_t {}_tV_u$ for all states $s,t,u$.

You can find the shortest word in a context-free grammar by a simple iterative algorithm. For each grammar symbol $T$, let $\ell(T)$ denote the length of the shortest word generated by $T$, i.e., the shortest word in $L(T)$; we assume $\ell(a)=1$ for all terminals. As a notational convenience, if $\alpha=\alpha_1\cdots \alpha_k$ is a string of terminals and non-terminals, set $\ell(\alpha)=\ell(\alpha_1)+\dots+\ell(\alpha_k)$. Initially, set $\ell(T) := \infty$ for all nonterminals $T$ and treat all rules as unmarked. Then, repeat the following. Pick an unmarked rule $A \to \alpha$ where $\ell(\alpha)<\infty$, set $\ell(A) := \min(\ell(A), \ell(\alpha))$, and mark that rule. Repeat until convergence. After this is finished, $L(S)$ tells you the length of the shortest word output by the grammar, if $S$ is the start symbol of the grammar. You can augment the algorithm to keep track of the word itself as well as its length, and then you'll be able to output the shortest word in the grammar.

This might be handy for your application, because it gives you the shortest counterexample: the shortest string that has balanced parentheses but isn't accepted by your regexp.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ That’s, um, incredible? Idk why I didn’t think to phrase the problem this way; I am certainly aware of the properties in your first paragraph! Thank you especially for the details; this gives me much to go on. When I eventually get this working, I may compare it to a QuickCheck version :P $\endgroup$ – D. Ben Knoble Jan 17 at 23:02

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.