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...

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ so would a push down automata work i.e are the languages Deterministic context-free? $\endgroup$
    – beoliver
    Commented Jun 23, 2017 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. ♦
    Commented Jun 23, 2017 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.