1
$\begingroup$

Show if $L = \{a^mb^nc^n \mid m,n \geq 0\} \cup \{b,c\}^*$ is regular or not.

My attempt:

I think the Pumping lemma won't work in that constellation, so I'm working with "The intersection of regular languages is regular".

Assuming $L$ is regular. I already know that $S=\{ab^* c^*\}$ is regular. I'll now look at the intersection $L \cap S$.

$$(\{a^mb^nc^n \mid m,n \geq 0\}\cap \{ab^* c^*\}) \cup (\{b,c\}^*\cap \{ab^* c^*\})$$ $$\{ab^nc^n \mid n \geq 0\} \cup \emptyset = \{ab^nc^n \mid n \geq 0\}$$

Which is not regular according to Pumping lemma. Is this idea correct?

$\endgroup$
8
  • 1
    $\begingroup$ Yes your idea is correct and is a good way to go. Just a detail: $S$ should be defined as $S = ab^*c^*$, not $S = \{ab^*c^*\}$ (or maybe $S = \{a\}\{b\}^*\{c\}^*$ if you want to show the difference between regular expression and language). $\endgroup$
    – Nathaniel
    Commented Mar 20, 2021 at 19:34
  • $\begingroup$ @Nathaniel yes, I should better write like you suggested. Thank you. (If you had an answer I'd tick it) $\endgroup$ Commented Mar 20, 2021 at 22:10
  • 1
    $\begingroup$ I just confirmed your thoughts, it's okay if I don't get an upvote :-) $\endgroup$
    – Nathaniel
    Commented Mar 21, 2021 at 0:29
  • $\begingroup$ We discourage "Please check whether my answer is correct" questions, as they are unlikely to be useful to others in the future. $\endgroup$
    – D.W.
    Commented Mar 21, 2021 at 2:31
  • $\begingroup$ @D.W. But if I don't include my own work, people will tell me to do so or say something like "If you don't include your own work, it looks like you're looking for someone to do your homework" $\endgroup$ Commented Mar 21, 2021 at 12:04

2 Answers 2

0
$\begingroup$

Pumping lemma works easily. Somewhere it says "if the language is regular then for every string in the language..." Just check the pumping lemma for strings that start with exactly one a.

$\endgroup$
1
  • $\begingroup$ Try carrying out the proof to see what goes wrong. $\endgroup$ Commented Mar 28, 2021 at 14:20
0
$\begingroup$

There are stronger versions of the pumping lemma that do apply directly to your language. For example, Wikipedia describes the following pumping lemma:

If $L$ is regular then there is a constant $p$ such that any word $uwv \in L$, where $|w| \geq p$, can be decomposed as $uxyzv$ so that (i) $|xy| \leq p$, (ii) $y \neq \epsilon$, (iii) $uxy^tzv \in L$ for all $t \geq 0$.

Using this, let us prove that your language is not regular. Let $p$ be the constant promised by the lemma. Take the word $ab^pc^p$, where $u = a$, $w = b^p$, $v = c^p$. According to the lemma, we can decompose $w = xyz$ in such a way that $y \neq \epsilon$ and $uxy^tzv \in L$ for all $t \geq 0$. However, if $y = b^q$ then $uxy^0zv = ab^{p-q}c^p \notin L$, since $q \neq \epsilon$.

There should be an even stronger pumping lemma along the lines of Ogden's lemma, which is a strong analog of the pumping lemma for context-free languages. You can formulate and prove it, if you wish.

$\endgroup$

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.