Given a transition table do digraph, determine if it is DFA or NFA and build grammar

Question

For the next transition table:

$$\begin{array}{|c|c|c|c|}\hline&0&1&2\\\hline a&a&b&d\\\hline b&a&b&c\\\hline c&c&d&a\\\hline d&c&c&a\\\hline\end{array}\\a\text{ is initial state}\\\{a,d\}\text{ are final states}$$

1. Make the digraph of the finite automaton and indicate if it is DFA (deterministic) or NDFA (non-deterministic).

2. Build a regular grammar that generates the language recognized by the automaton and indicate it.

---

1. The digraph I made is:

where $\mathrm{start}=a$, $\,s0=b$, $\,s1=c$, $\,s2=d$ and the states marked with a tick are final states.

The finite state machine (which is an automaton) $A=(\{a,b,c,d\},\{0,1,2\},\delta,a,\{a,d\})$, where $\delta:\{a,b,c,d\}\times\{0,1,2\}\to\{a,b,c,d\}$ is deterministic because each state has at most one change of state for each letter of the alphabet and there are no state changes for the null word.

2. A regular $\require{cancel}\cancel{\text{grammar}}\text{ expression}$ could be: $$\require{cancel}\xcancel{\begin{align*}L(A)&=0^*\\&\vee2^*\\&\vee(220^*2^*)^*\\&\vee(11^*0)^*\\&\vee(11^*20^*\vee2)^*\\&\vee(11^*20^*\vee(12))^*\\&\vee(11^*20^*\vee1)^*.\end{align*}}$$ \begin{align*}a&=0^*\vee1b\vee2d\vee\lambda\\b&=1^*\vee0a\vee2c\\c&=1d\vee2a\vee0^*\\d&=1c\vee0c\vee2a\vee\lambda\end{align*} and from here I do not know how to build the regular expression and then build the regular grammar (I have seen this and this links but I do not understand them since I could not even get the regular expression) because I have never seen an automaton with $2$ final states!!

Also, the statement what does it mean by indicating the regular grammar?

Everything is correct?

Thanks!

External link:

1. Automaton created by automatonsimulator.com. You can test it introducing words here.

Answer 1

Using FSM2Regex, I encoded your transition table:

#states
a
b
c
d
#initial
a
#accepting
a
d
#alphabet
0
1
2
#transitions
a:0>a
b:0>a
c:2>a
d:2>a
a:1>b
b:1>b
b:2>c
c:0>c
d:0>c
d:1>c
a:2>d
c:1>d

The resulting state transition graph:

And the generated regular expression:

2+2((0+1)(0+1(0+1))*(1+2+12)+2)+11*(2(0+1(0+1))*(1+2+12)+0)+(0+$+2(2+(0+1)(0+1(0+1))*(2+12))+11*(0+2(0+1(0+1))*(2+12)))(0+2(2+(0+1)(0+1(0+1))*(2+12))+11*(0+2(0+1(0+1))*(2+12)))*(2+2((0+1)(0+1(0+1))*(1+2+12)+2)+11*(2(0+1(0+1))*(1+2+12)+0)+0+$)+0+$

In FSM2Regex syntax, a valid regex consists of alphanumeric characters representing the set of input symbols (here 0, 1, 2), the $ character representing the empty string, the choice operator +, the Kleene operator *, and parentheses ( and ).

The state machine is deterministic. There are no ambiguous state transitions where the machine has a choice which state to assume next.

See here for a definition of a regular grammar. Note that a grammar and a regular expression possibly can be converted to each other but are different concepts.

To derive a regular expression, several algorithms or visual methods exist. See this post for a detailed explanation. Basically, internal (= non-initial and non-final) states are removed step-by-step. Result is a state transition diagram or table with only the initial and one or more final states. The transition condition from initial to a final state is the regular expression.