# Timeline for How to prove that $\{\$x\$\}$ is a regular language if $x$ is derived from $L=\{w\}$ by substituting substrings?

### Current License: CC BY-SA 4.0

11 events
when toggle format what by license comment
Jan 28 '19 at 21:13 comment Updated with a few corrections of typos.
Jan 28 '19 at 21:07 history edited
Fixed several typos.
Jan 28 '19 at 21:05 comment I understand the transitions now, thanks! I still don't why you concatenate dollar sign here: $\delta_D((q, s_1), \$)= (\delta_L(q, 1), s_0)\$$? Jan 28 '19 at 21:00 history edited Fixed a typo. Jan 28 '19 at 20:58 comment Exactly. That is why incomplete DFA is popular since there is no need to write any transition that goes to a dead state. In fact, we do not have to specify that dead state. Jan 28 '19 at 20:55 comment and the way we make sure that words that contain 01 for example are not accepted in your example is that you don't have \delta_d((q, o), 1)=... state right? Jan 28 '19 at 20:51 history edited [Edit removed during grace period] Jan 28 '19 at 20:47 comment If we know the last letters of the words that reaches a state s, then we can specified what will be the next state if the word is extended with another letter. Note that we must ensure words containing 01 and words with isolated \$$ should not be accepted.
Jan 28 '19 at 20:38 comment Can you please explain why do you have states based on what letter reached the end of the words? For example, I'd define the transition functions as follows: $$\delta_D((q,2),0)=(\delta(q,2),0)\\\delta_D((q,\),0)=(\delta(q,0),1)\\\delta_D((q,\),1)=(\delta(q,1),0)$$.In my example we start out with state $0$. When we read the first $\$$we flip the state to 1. When we read the second \$$ we flip the state back to$0$. When we read$2$nothing changes so we stay in state$0$as well. In the end we can add$\'s from the beginning and end of each word.
Jan 28 '19 at 20:17 history edited