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

At the time of writing this, the crossed out answer in the question is a regular expression, but your new answer is almost the correct regular grammar! (almost because production rules should not have Kleene star, unlike as you wrote in $a=0^*\ ...$) Using your notation, a full specification/"indication" of the regular grammar should be the following:

• Terminal Symbols: $0,1,2$
• Non-terminal Symbols: $a,b,c,d$
• Production Rules (incomplete; please fill-in):

$$\begin{align*}a&\rightarrow0a\vee1b\vee2d\vee\lambda\\b&\rightarrow 1b\vee0a\vee2c\\c&\rightarrow\ ...\\d&\rightarrow\ ...\end{align*}$$

• Start Symbol: $a$

Edit: Now I see that the "indicating it" part of question #2 is confusing. Unless "indicating" is formally defined in your class (very unlikely), I think the better thing to do in case something like this happened in exam is to ask the examiner for clarification (e.g. "Does indicate mean to show the tuple?").

On my comment about "if I were to take the exam", treat it as "according to my own understanding of the question" and as I understand question #2, indicating the grammar just means complete specification of the 4-tuple.

Answer 2

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.