0
$\begingroup$

I have two languages as below.

$$L_1=\{a^ncb^n\}\cup\{a^mdb^{2m}\}$$ $$L_2=\{a^{2n}cb^{2m+1}\}\cup\{a^{2m+1}db^{2n}\}$$

Now, I wonder what is $L_1\cap L_2$. Is it a regular language? Is it context-free?

To solve the problem, I feel like I need to solve the following system of equations, but I'm not sure.

$$ \begin{cases} 2n=2m+1\\ 2m+1=\frac{2n}{2} \end{cases} $$

Improve this question
$\endgroup$
1
  • $\begingroup$ Note that these are not regular expressions; neither of the involved languages is regular! If you don't see why, you need to reread some of your material. $\endgroup$
    – Raphael
    Commented May 11, 2017 at 13:17

2 Answers 2

Reset to default
2
$\begingroup$

$L_1=\{a^ncb^n\}\cup\{a^mdb^{2m}\}$

$L_2=\{a^{2n}cb^{2m+1}\}\cup\{a^{2m+1}db^{2n}\}$

If we say $\;L_1=L_{11}\cup L_{12}\;\:$and$\;L_2=L_{21}\cup L_{22}$

$L_1\cap L_2=((L_{11}\cap L_{21})\cup (L_{12}\cap L_{21}))\cup ((L_{11}\cap L_{22})\cup (L_{12}\cap L_{22})) $

$L_{11}\cap L_{22}\:,\:L_{12}\cap L_{21}\;$will be zero because d and c are different symbols.

So $\;L_1\cap L_2=(L_{11}\cap L_{21})\cup (L_{12}\cap L_{22}) $

$L_{11}\cap L_{21}=\emptyset \:\;$because it is not possible for an even number to be equal to an odd number.

$\;L_1\cap L_2=L_{12}\cap L_{22}=L=\{a^{2m+1}db^{4m+2}\}$

So the language is not regular but context free. It is impossible to construct a finite automaton for this language because finite automaton has a memory that is fixed and cannot thereafter be expanded. ( It cannot store number of a's ) But it is easy to recognize that L is context free since $L=(a(aa)^*db^*)\cap \{a^ndb^{2n}|n\geq 0\}$ ( intersection of a CFL with a regular language is CFL ) And $ \{a^ndb^{2n}|n\geq 0\} $ is context free because there exists a push-down automaton that accepts L. When this automaton sees an $\:a\:$ it pushes 2 $\:a\:$'s into the stack and when $\:d\:$ is the input it changes it's state to a final state and then for each $\:b\:$ it pops an $\:a\:$ from the stack.

Improve this answer
$\endgroup$
1
$\begingroup$

Any string in the intersection of $L_1$ and $L_2$ must be in either the first subset of $L_1$, hence has a 'c' in the middle, hence is ALSO in the first subset of $L_2$, OR [by similar reasoning] is in the second subsets of $L_1$ and $L_2$. A string in the first subset of $L_1$ has equal numbers of 'a'-s and 'b'-s, while a string in the first subset of $L_2$ has an even number of 'a'-s and an odd number of 'b'-s, hence an UNequal number of 'a'-s and 'b'-s. Therefore there is NO string which is in the first subsets of both $L_1$ and $L_2$.

To be in the second subsets of both $L_1$ and $L_2$ IS possible: the number of 'b'-s must be twice the number of 'a'-s (by $L_1$), and this is possible with $L_2$ if $n_1$ is odd and $n_2$ = $2m_2+1$ = $n_1$ [where '$n_i$' means 'the $n$ in $L_i$' etc]. Therefore the language of the intersection is equal to the set of strings of the form $a^{2m+1}db^{4m+2}$, which is regular.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ I notice that you seem to be posting quite a few answers but from different accounts. Is there any chance you could register an account and just use that one? The advantage from your point of view is that you get to collect all your reputation in one place, which opens up features of the site. The advantage from our point of view is that answers from new users get automatically put into a queue for approval so you posting from multiple accounts does actually create work for people. $\endgroup$
    – David Richerby
    Commented May 10, 2017 at 19:34
  • $\begingroup$ "which is regular" -- how do you come to that conclusion? $\endgroup$
    – Raphael
    Commented May 10, 2017 at 19:52
  • $\begingroup$ I assume $a^{2m+1}db^{4m+2}$ is a regular language because it can be represented by a regular expression, is it right? $\endgroup$
    – Megidd
    Commented May 11, 2017 at 4:29
  • 2
    $\begingroup$ @user4838962 The conclusion would be correct, but that's not a regular expression. Note how $m$ appears on both sides; this language is exactly as hard to parse as $a^n b^n$. $\endgroup$
    – Raphael
    Commented May 11, 2017 at 5:21
  • 1
    $\begingroup$ $a^x$ isn't always, but that's not the point. We could agree that $a^n b^m$ is a regular expression in a certain sense, but $a^n b^n$ is not -- you can't re-use the same exponent! While you can certainly define a syntax for expressions this way, they do no longer define regular languages, hence they are not regular expressions. In fact, $a^nb^n$ is the textbook example for a non-regular language, and $a^nb^nc^n$ is the textbook example for a non-context-free language. You have sever gaps in your fundamentals in this area! $\endgroup$
    – Raphael
    Commented May 11, 2017 at 13:19

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.