Skip to main content
2 of 2
Commonmark migration

Describe construction of finite automata that accepts the language Double-Letter(L)

Describe construction of finite automata that accepts the language Double-Letter(L), where Double-Letter(L) is in the language of words from L, except each letter in the word appears twice. So $abc\in L$ $\iff aabbcc \in $ Double-Letter($L$).

For example if L={a,aa,ab,ba} then Double-Letter(L) = {aa,aaaa,aabb,bbaa}

My idea: Create states Q that are named s and ss where $s\in \Sigma$. Make states named ss accepting if $ss \in L$

FA illustrated for the example above

What next? is this a good approach? I can't think of the next step on how to construct this doubled DFA for ALL languages.

Mandy
  • 177
  • 7