1
$\begingroup$

I'm a bit new to automata theory, I'm sorry if this question is a bit too simple. If this question has been answered somewhere already, please point me to it.

One basic problem I wanted to solve was defining the minimal set of states need to construct a (minimal) DFA that accepts

$$(a^+)+bcd^*\,.$$

I'm not sure how to treat the OR operator here, though.

I assume it means I can accept either ($a^+$) OR $bcd^*$ OR both (but in the given order), but does it mean I can ignore the order as well (meaning that, e.g. $bcdddaa$ would be acceptable as well)?

If anyone could explain, I would appreciate it. I understand the meaning of other operators.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I edited your question very slightly: really, it's a question about regular expressions, not automata. You need to understand this regular expression because of something you want to do with automata, but the question is all about the regexp stage of the process. $\endgroup$
    – David Richerby
    Jul 10 '18 at 16:26
  • $\begingroup$ I like to think of it as a branch where you shoot off into two parallel computations. So after your start state you would have two transitions, one on a and one on b where you would then check the rest of the regular expression corresponding to the left and right side of the + $\endgroup$
    – Mitch
    Jul 27 '18 at 15:35
1
$\begingroup$

You're confusing "or" with concatenation. Also, In computer science, a string matching a regular expression means that the whole string matches whereas regular expressions used in computer software usually just require some part of the string to match the expression.

A string matches $a^+$ if the whole string is composed of $a$s and nothing else, and there's at least one $a$. A string matches $bcd^*$ if it consists of a $b$ followed by a $c$ followed by zero or more $d$s and nothing else.

A string matches $a^++bcd^*$ if it matches $a^+$ or it matches $bcd^*$ or if it matches both. However, it's not possible to match both: a string can't be composed entirely of $a$s and also begin with a $b$ and a $c$.

In particular, $aabcdd$ doesn't match $a^++bcd^*$ because it doesn't match $a^+$ (it contains characters that aren't $a$) or match $bcd^*$ (it doesn't even begin with $b$). However, $aabcdd$ does match $a^+bcd^*$, which is the concatenation of $a^+$ and $bcd^*$. $bcddaa$ matches neither $a^++bcd^*$ nor $a^+bcd^*$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Re, "...regular expressions used in computer software..." Regular expressions used in computer software don't require anything. Regular expression libraries typically provide a number of different functions that operate on a string and an RE. One such function might search within the given string to find a substring (if any exists) such that the whole substring matches the RE. Another such function might return a list of such substrings, and another might simply return a boolean indicating whether such a list would be empty or non-empty. Other functions deal with "capture groups", etc. $\endgroup$
    – Solomon Slow
    Jul 10 '18 at 21:13
  • $\begingroup$ @jameslarge Whether software is implemented as a library or some other way is irrelevant to what I’m talking about. The fact that other behaviour is possible is covered by my use of “usually”. $\endgroup$
    – David Richerby
    Jul 10 '18 at 21:52
  • $\begingroup$ You're right. Implementation is irrelevant. My point is, that what a simple RE means is the same, wherever you encounter it. An RE specifies a language (i.e., a set of strings). Strings that are members of the language are said to match the RE. Many programming environments provide a function, handy for writing ad-hoc parsers, that searches within a given string, to find substrings that match a given RE. Some environments also provide a function, generally less interesting, that tests whether a given whole string is a match. $\endgroup$
    – Solomon Slow
    Jul 10 '18 at 22:21
  • $\begingroup$ Practial RE engines also provide enhanced features, such as "anchors" and "capture groups," that help a lot with those ad-hoc parsers, but which are not so relevant to a computer science-y discussion. $\endgroup$
    – Solomon Slow
    Jul 10 '18 at 22:23
  • 1
    $\begingroup$ @jameslarge Ok, great. I still contend that the most common experience of regular expressions for software users and programmers is “string matches if it contains a matching substring”, whereas the CS meaning is “string matches if the whole string matches.” $\endgroup$
    – David Richerby
    Jul 10 '18 at 22: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.