patternMinor
To build a special unary regular expression
Viewed 0 times
expressionregularunaryspecialbuild
Problem
Say that there's a prime number P,
And we can easily build an unary regular expression [E0]for every number that is divisible by P:
E0::= (aaaa...a)*,with p "a",
The question is, how do we build the opposite unary regular expression [E1], for every number that isn't divisible by P?
Do I need to build the E1 by listing all the number mod p=1,2, to p-1, or there can be a easier way to build it ?
And we can easily build an unary regular expression [E0]for every number that is divisible by P:
E0::= (aaaa...a)*,with p "a",
The question is, how do we build the opposite unary regular expression [E1], for every number that isn't divisible by P?
Do I need to build the E1 by listing all the number mod p=1,2, to p-1, or there can be a easier way to build it ?
Solution
There is a "smart" way of following your approach:
$$
(a^p)^*a(\epsilon+a)^{p-1}
$$
Here $r^p$ is shortcut for $r$ concatenated $p$ times.
This regular expression has length $O(p)$. On the other hand, using the pumping lemma it is not hard to show that the minimal NFA for the language contains at least $p$ states, and this gives a lower bound of $\Omega(p)$ on the size of a regular expression for the language, since a regular expression can be translated to an NFA with only a constant multiplicative blow-up in size.
$$
(a^p)^*a(\epsilon+a)^{p-1}
$$
Here $r^p$ is shortcut for $r$ concatenated $p$ times.
This regular expression has length $O(p)$. On the other hand, using the pumping lemma it is not hard to show that the minimal NFA for the language contains at least $p$ states, and this gives a lower bound of $\Omega(p)$ on the size of a regular expression for the language, since a regular expression can be translated to an NFA with only a constant multiplicative blow-up in size.
Context
StackExchange Computer Science Q#63881, answer score: 4
Revisions (0)
No revisions yet.