Is it a solvable problem to generate a regular expression that matches some input set?
- by Roman
I provide some input set which contains known separated number of text blocks.
I want to make a program that automatically generate 1 or more regular expressions each of which matches every text block in the input set.
I see some relatively easy ways to implement a brute-force search. But I'm not an expert in compilers theory. That's why I'm curious:
1) is this problem solvable? or there are some principle impossibility to make such algorithm?
2) is it possible to achieve polynomial complexity for this algorithm and avoid brute forcing?