How do I construct transition table for the following?

1,415

So from your description we need four states:

  • A start state $s_\epsilon$, it signals that nothing has been read
  • A state $s_0$ that signals that the word started with a $1$, and the last read symbol was a $0$.
  • A state $s_1$ that signals that the word started with a $1$, and the last read symbol was a $1$.
  • A state $s_\bot$ that signals that the word started with a $0$.

If we have started with a $0$, nothing ever read can lead to an accepted word, that is we stay in $s_\bot$, that gives the transition table $$ \begin{array}{c|*4c} & s_\epsilon & s_0 & s_1 & s_\bot\\ \hline 0 & s_\bot & s_0 & s_0 & s_\bot\\ 1 & s_1 & s_1 & s_1 & s_\bot \end{array} $$

Share:
1,415

Related videos on Youtube

Neet
Author by

Neet

Updated on November 23, 2020

Comments

  • Neet
    Neet almost 3 years

    Fig. contains transition diagramDesign Finite Automata which accepts only those strings that start with 1 and ends with 0. Please describe me how to construct transition table because all I need to learn is transition table itself as I can then draw transition diagram from the table.

  • Neet
    Neet almost 7 years
    Thanks for the answer. Here, you have mentioned 4 states but in my text book it says there are 3 states that is A,B and C where they have drawn transition diagram but transition table is not provided, so can you please explain it accordingly? I want to know how transition table is created.
  • martini
    martini almost 7 years
    You have a transition diagram? Can you add it to your question? And - as it stands - an automaton that does what you want needs four states.
  • Neet
    Neet almost 7 years
    Yes. I have added a link to the description.
  • martini
    martini almost 7 years
    So your description of automata allows for the transition function to be undefined at some points. Note that $\delta(A, 0)$ is not defined. The "undefined state" I called $s_\bot$, in your case, we can read of the transition table from the diagram, giving: $$ \begin{array}{c|*3c} & A & B & C \\ \hline 0 & \bot & C & C\\ 1 & B & B & B\end{array}$$ So my $s_\epsilon$ corresponds to $A$, my $s_0$ to $C$ and $s_1$ to $B$.
  • Neet
    Neet almost 7 years
    I know because when I drew the diagram then in state A if i read 0 it goes to state C and according to my text book state A has no 0. Thanks for making it clear. Need to practice creating transition table. Can you please tell me what are the steps to create transition table from a given question?