1
$\begingroup$

How can I prove that this language is regular, possibly by making a finite automata for this: $(ab)^*(cb^n)^*$, where $n\ge1$?

An automaton can easily be drawn for the part $(ab)^*$, but the part $(cb^n)^*$ doesn't seem to be regular because if the Kleene closure is taken $\ge2$ times, then it will be of the form $(cb^n)(cb^n)$, which reduces to string matching and is context-sensitive.

This was actually a question, solution to which said that the above language has the following regular expression: $(ab)^*(cbb^*)^*$.

Improve this question
$\endgroup$
10
  • 2
    $\begingroup$ There is an ambiguity in $(cb^n)^*$. Does it mean words like $cb^ncb^n\cdots cb^n$ or $cb^{n_1}cb^{n_2}\cdots cb^{n_k}$, where $n_i\ge1$? If it is the former, then the language is not regular and cannot be accepted by a finite automaton! However, if we consider $C$ is the languages of words of the form $cb^n$ where $n\ge1$, then $C^*$ should be interpreted as the the latter, by the definition of Kleene closure. Can you provide a url or reference to the original problem? $\endgroup$
    – John L.
    Commented Nov 19, 2018 at 18:54
  • $\begingroup$ With a moment of reflection, it seems the only interpretation that can make sense is the latter. The former is not compatible with the usage of parenthesis (meaning, highest priority) and the definition of Kleene star. $\endgroup$
    – John L.
    Commented Nov 19, 2018 at 19:03
  • $\begingroup$ @Apass.Jack I can't give url as it was a question from an online practice test. But the explanation given in the solution said that it's regular since it can be written like $(ab)^*(cbb^*)^*$, which is basically the latter interpretation. $\endgroup$
    – virmis_007
    Commented Nov 19, 2018 at 19:12
  • 1
    $\begingroup$ @virmis_007 If you want to know how to interpret the question, you should ask the person who set it to you, not us, and point out that their notation is ambiguous. $\endgroup$
    – David Richerby
    Commented Nov 19, 2018 at 20:16
  • 1
    $\begingroup$ @DavidRicherby, I believe you meant How to create DFA from regular expression without using NFA? or Convert regular expression to DFA. $\endgroup$
    – John L.
    Commented Nov 20, 2018 at 2:31

1 Answer 1

Reset to default
0
$\begingroup$

For the correct/sensible interpretation, $(ab)^*(cbb^*)^*$, I will list the states and its corresponding regular expressions below; you can figure out the transitions between the states.

$q_{0}$: $(ab)^*$, start state
$q_{1}$: $(ab)^*a$
$q_{2}$: $(ab)^*(cbb^*)^*c$
$q_{3}$: $(ab)^*(cbb^*)^*$, accepting state
$q_{4}$: for all other strings, rejecting state/dead-end state

For the incorrect/unlikely interpretation, where $(cb^n)^*$ means all words like the empty word, $cb^n$, $cb^ncb^n$ and $cb^ncb^n\cdots cb^n$ for some $n\ge1$, the corresponding language is not regular since its intersection with the language with regular expression $cb^*cb^*$, $\{cb^ncb^n\mid n\ge1\}$ is not a regular language. So there is no FSA for that language.

Improve this answer
$\endgroup$

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