World's most popular travel blog for travel bloggers.

Automaton for 'almost' same word in language

, , No Comments
Problem Detail: 

I have some finite language L, which is regular.

I want to find a finite automaton (DFA/NFA) that for every word w in L, it accepts any word with the same length but only with 1 char diffrence.

I thought about maybe accept DFA for L, because it a regular language and think about an NFA solution, but my problem is those possible "circles" in the automata..

Any idea?

Asked By : Ori Refael
Answered By : Ran G.

Main Idea:
Construct two copies of the DFA for $L$. The first copy will be connected to the second copy by moves that will allow the "difference" of a single letter. For example, if $q_1$ and $q_2$ are connected by a $0$-move in the original DFA, then $q_1$ in the first copy will be connected to $q_2$ in the second copy by a $1$-move.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback