1
$\begingroup$

in my practice for a test I came across this question: prove or disprove that those languages are regular:

enter image description here

I succeeded proving that the second language is nonregular with homomorphism but i'm having trouble with the other 2 -

  1. my intuition tellin me that first 1 is Σ∗ but i'm really stuck on how to prove it

  2. (not sure why it writes 2 when i'm writin 3 haha) in this one i'm really stuck - my intuition is tellin me again that it will be finite automaton (automata? sorry if my english is not so good) and therefore regular language but how can I prove it? how can I use the fact that |w| is bounded? - i guess I need to build an automaton , maybe with some "flags" but I suck at it (for now) :[.

does ww^R is regular language when |w| is bounded? I've looked a lot (through google in this site) for an answer for this question but I havent find something - only that this language is not regular when |w| is not bounded.

Can I get some hints on both of those languages please?

$\endgroup$
2
$\begingroup$

For number 1, you're entirely correct. Every string in $\Sigma *$ is in this language. Take an arbitrary string of zeroes, ones, and twos, then let $y$ be that string, and $w$ be empty.

For number 2, the standard way I learned to prove it's not regular is with "fooling sets". The Pumping Lemma also works here.

For number 3, consider that there are only finitely many possibilities for $w$. This means you could, in theory, write a regular expression that just listed all of them. So this one is actually regular, through "brute force".

$\endgroup$

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.