Question

For Automata class:

Let L be a regular language over the binary alphabet. Consider the following language over the same alphabet: L' = {w | |w| = |u| for some u ∈ L}. Prove that L' is regular.

Answer 1

Your Explanation :

------------------------

L is regular, there is a DFA D that accepts the language L

For each transition in DFA having

A -> B on symbol x

Change it to have each and every symbol in the alphabet

For example if A -> B is on 0
Alphabet is {0, 1}

Make it like
A -> B on 0
A -> B on 1

This way we have an NFA now which accepts the language L0.

So, L0 is regular.

------------------------------------------------------------------------------------------------------------

Note : Please thankful the answer, if you like it, as it would be of great help to me..!!

------------------------------------------------------------------------------------------------------------