Regex expression

Let L be the language over the alphabet {0, 1, 2, 3, (,), +, -, *, /}, L is the set of operations with correctly formatted natural numbers (a single number is considered to belong to L, 2 – – 3 is an incorrect expression, 2 + 3 is correct, 2 + (-3) is correct. Is it possible to write a regular expression for this language? If not, why?

I think that it is not possible to write a regular expression for this language, because of the operator / we not write 2 / 0 for exemple and are more than a finite number combinations to make this possible. It is correct so?

Simplifying the Boolean expression $A + \bar{A}\bar{B}$?

So I’m trying to simplify the Boolean expression (1) $ A + \bar{A}\bar{B}$ .

I noticed that by Karnaugh maps this is equivalent to $ A+\bar{B}$ , and I also noticed that if I take the complement of (1), I get ~(1)= $ \bar{A}(A + B) = \bar{A}A + \bar{A}B = \bar{A}B$ , so then taking complements again yields (1) = $ A + \bar{B}$ .

But this feels very ad hoc to me, and makes me feel like I’m missing some key point about how to simplify this expression more systematically.

Any thoughts appreciated.


Algorithm to Minimize a Regular Expression

I am referring to regular expressions with alphabet {$ 0$ , $ 1$ }. We want to minimize them so that they have the least possible number of symbols and operators. Is there an algorithm to do this?

For instance, what is done on this page in the accepted answer:

Is there a formal algorithm to explain the process that the answer went through?

Error: Expected a right parenthesis in expression at (1) after `make` command

I am compiling a software following this tutorial (called PRESTO), but when I type ./configure, I receive the following message:

$   make && sudo make install Making all in src make[1]: enter directory "/home/user/Softwares/tempo/src" /usr/bin/f77  -g -O2 -c -o bnryddfwhiecc.o bnryddfwhiecc.f bnryddfwhiecc.f:130:71: Error: Expected a right parenthesis in expression at (1) Makefile:468: set of instructions for the objective "bnryddfwhiecc.o" failed  make[1]: *** [bnryddfwhiecc.o] Error 1 make[1]: exit directory "/home/user/Softwares/tempo/src" Makefile:359: set of instructions for the objective "all-recursive" failed make: *** [all-recursive] Errore 1 

I believe it has to do with the excessive length of the lines in the code. I have tried to add a & character to the sixth column of the “following” line, or right after the end of the long line, basically what is said here, but did not work.

I would rather use a command to disable the long-lines errors, instead of going to modify each line of each file. But I do not know enough to take actions.

Minimal regular expression from minimal NFA for finite language in polynomial time?

Given a minimal NFA for a finite language, is there a polynomial-time algorithm to find a minimal regular expression for the same language?

This question is based on a recent question regarding minimization of regular expressions for finite languages given a regular expression. I was surprised to learn there don’t appear to be any stronger results. (see Is there a polynomial-time algorithm to minimize regular expressions without Kleene closures/stars?)

Regular expression with no backtrack

I’m trying to understand if “non backtracking regular expressions” are less expressive than the “regular expressions” we are all used to.

For example, let’s say that matching is greedy and no backtrack is allowed; the expresson a?a would match the string "aa" but would not match the string "a" because a? will eat up the a and there will be nothing left to match.

However, there is a way to match “one or two ‘a'” with a non backtracking expression: aa?. Now, for the string "aa" a will consume the input and a? will succeed anyway.

I can’t come up with an example of a “normal” regular expression that I couldn’t re-write in a “non-backtrack” fashion, so I’m tempted to think that the two are equivalent. Of course, I can’t be sure.

I’m wondering if there is a way to prove (or disprove) that every language that can be described by a regular expression with backtraking can also be described by a regular expression with no backtraking.

Anyone knows?

Error “illegal start of expression” en NetBeans

estoy programando una aplicacion y me tira el error “illegal start of expression”, por lo que deduzco que debe ser un error de escritura pero no lo encuentro. Aca abajo dejo el segmento del codigo que me causa este error:

`public static void main(string args[]){     java.awt.EventQueue.invokeLater(() -> {         new ventanauno().setVisible(true);     });