0
$\begingroup$

Problem

In the problem, I was given the grammar for a non-deterministic finite state automata (NDFSA). There was no other useful context given. The problem asks you to use this grammar to draw the NDFSA and then asks you to convert the NDFSA into a deterministic finite state automata (DFSA). The grammar is written as such:

G2[E]:
E ::= De | Ee | Ef
D ::= Ad | Ef
B ::= De | c | a | Bc
A ::= Ef | a

and I will attach a picture of the drawing I have of the NDFSA.

My drawing of the NDFSA

My Question

The problem I am having is that I do not understand which of these states are the final or accepting states and what qualifications a state must meet to be a final state.

I have been assuming that the final state is the one listed in the square brackets in the title of the grammar (because that was the case for the problem we did in class), but I am unsure if this is correct.

Other questions posted here mention that a final state is just a way of knowing if the input is a valid sentence for the given grammar (if and only if the last character of input leaves us in a final state), but I am more concerned with why is a final state a final state or if the problem should give (or already gives) me the final state(s).

Are final states only final states because the grammar says so, or is there something that I am missing?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ It's a final state because if you have detected an E (and nothing else) then it means the input matches the grammar. The one in square brackets is the main one that is the whole grammar. $\endgroup$
    – user253751
    Feb 1 at 20:22
  • 1
    $\begingroup$ The accepting states cannot be determined just from the grammar. The grammar only tells which sentences are legal. $\endgroup$
    – Yves Daoust
    Feb 2 at 12:50
  • $\begingroup$ So, from what I understand the [E] denotes that it is the main final state for the whole grammar and I'm not able to mark final states when only given the grammar. Is there any other criteria I should be looking for or am I overthinking this? $\endgroup$
    – Brett Smith
    Feb 2 at 17:12
  • $\begingroup$ Grammars don't have states, automata do. They both describe languages. the [E] here may indicate that E is indeed the designated non-terminal/variable from which to start all derivations. $\endgroup$
    – Kai
    Feb 3 at 11:52

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.