0
$\begingroup$

Determine two languages L and L1 on the alphabet {a,b} with regular L, L∩L1 is non-regular and L1 does not contain L.

I came up with this solution: L = { w | w ends with the string aba} L1 = {w | w = w^r (palindrome) }

L∩L1 = {w | w ends with the string aba AND w is palindrome}

I don't know if this is correct as a solution, perhaps you also have simpler examples? Thank you.

Improve this question
$\endgroup$
1
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. In the future it's better to ask about a specific conceptual issue you're uncertain about. As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W. ♦
    Commented Dec 14, 2023 at 20:04

1 Answer 1

Reset to default
0
$\begingroup$

It’s very easy really.

Take any non-regular language L1, and then the regular language of all strings (a | b)*. The intersection is L1.

If you want neither language to be a subset of the other, take a short string S in the non-regular language and use the regular language “all strings other than S”.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for your answer, but this way if I choose any non-regular language e.g. L1 = {a^n b^n | n > 0} and L = {w | w ∈ {a,b}* } L1 will be contained in L? The exercise request states that L1 must not contain L $\endgroup$
    – Luca
    Commented Dec 14, 2023 at 14:37
  • $\begingroup$ @Luca gnasher729's answer is almost correct, except that the roles of $L$ and $L_1$ are reversed. Let $L$ be the set of all strings over $a, b$ and $L_1$ be any non-regular lnguage. Then $L_1$ will not contain all of $L$, though of course it will contain some of the strings of $L$ and $L\cap L_1=L_1$ will certainly be non-regular. $\endgroup$
    – Rick Decker
    Commented Dec 14, 2023 at 16:35
  • $\begingroup$ Thanks again, so i can write like this: L = { w | w ε {a,b}* AND w != aabb} L1 = {a^n b^n | n > 0} ? Can you also tell me if my first solution was correct? $\endgroup$
    – Luca
    Commented Dec 15, 2023 at 10:24

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.