1
$\begingroup$

Regular expressions are equivalent to DFA's and describe regular languages, but is the language used to construct regular expressions regular?

My guess is that the original syntax (concat, | and *) is, but the Perl-style syntax is not (backtracking). As the newer syntax recognises non regular languages they must also generate non regular languages. If a DFA could recognise a non regular language then there would be a problem...

$\endgroup$
2
$\begingroup$

Both "original syntax" and PCRE's syntax is not regular. You need parenthesis to override operator precedence, which puts your syntax language into the territory of context free languages.

$\endgroup$
  • $\begingroup$ so would a push down automata work i.e are the languages Deterministic context-free? $\endgroup$ – beoliver Jun 23 '17 at 9:31
  • $\begingroup$ @beoliver, that's a separate question, which should be asked in a separate post (see the 'Ask Question' button in the upper-right). However, before asking, you should first try to figure out the answer on your own. Write a grammar for the syntax, take a look at cs.stackexchange.com/q/265/755 and cs.stackexchange.com/q/18524/755, then try applying those methods to the grammar. If you're still stuck, then ask a new question, and show your progress so far and what you tried. You should be able to figure out whether it is context-free on your own based on that material. $\endgroup$ – D.W. Jun 23 '17 at 16:39

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.