Skip to main content
deleted 81 characters in body
Source Link
user80502
user80502

The single $a$ indicates that if we are in state $A$, and read $a$, we must go to an ending state, same with single $b$. If we follow that, we get this automaton :

enter image description here

If we were less prudent, we would argue that if we can generate an $a$ with variable $A$ and stop, and because $A$ is an ending state, then we can put a loop on state $A$ labeled with $a$, like this :

enter image description here

But this automaton doesn't match with grammar $G$. This one recognize strings of the form $a^i$, but grammar $G$ can't generate them.

But something that can be done to lighten our automaton would be to remove state $B_f$, and count on our ending state $A$ to handle the case where we end generation with a single $b$, like the following :

enter image description here

And that actually correct, because we have : empty word on variable $A$, and a rule $B \rightarrow bA$ (In fact, we can remove from $G$ the rule $B \rightarrow b$, because it can be replaced with $B \rightarrow bA \rightarrow \epsilon$).

FinallyEDIT : As @rici said, canif we doapply subset construction to the same with $A_f$ ? That is, remove it and put $B$ as an ending statelast automaton, like the followingwe get this one : (without dead states)

enter image description here

Unfortunately, we can't to that, because we can't end on variable $B$ with empty word. So the correct automatonthis is the penultimatean automaton that matches with $G$.

The single $a$ indicates that if we are in state $A$, and read $a$, we must go to an ending state, same with single $b$. If we follow that, we get this automaton :

enter image description here

If we were less prudent, we would argue that if we can generate an $a$ with variable $A$ and stop, and because $A$ is an ending state, then we can put a loop on state $A$ labeled with $a$, like this :

enter image description here

But this automaton doesn't match with grammar $G$. This one recognize strings of the form $a^i$, but grammar $G$ can't generate them.

But something that can be done to lighten our automaton would be to remove state $B_f$, and count on our ending state $A$ to handle the case where we end generation with a single $b$, like the following :

enter image description here

And that actually correct, because we have : empty word on variable $A$, and a rule $B \rightarrow bA$ (In fact, we can remove from $G$ the rule $B \rightarrow b$, because it can be replaced with $B \rightarrow bA \rightarrow \epsilon$).

Finally, can we do the same with $A_f$ ? That is, remove it and put $B$ as an ending state, like the following :

enter image description here

Unfortunately, we can't to that, because we can't end on variable $B$ with empty word. So the correct automaton is the penultimate.

The single $a$ indicates that if we are in state $A$, and read $a$, we must go to an ending state, same with single $b$. If we follow that, we get this automaton :

enter image description here

If we were less prudent, we would argue that if we can generate an $a$ with variable $A$ and stop, and because $A$ is an ending state, then we can put a loop on state $A$ labeled with $a$, like this :

enter image description here

But this automaton doesn't match with grammar $G$. This one recognize strings of the form $a^i$, but grammar $G$ can't generate them.

But something that can be done to lighten our automaton would be to remove state $B_f$, and count on our ending state $A$ to handle the case where we end generation with a single $b$, like the following :

enter image description here

And that actually correct, because we have : empty word on variable $A$, and a rule $B \rightarrow bA$ (In fact, we can remove from $G$ the rule $B \rightarrow b$, because it can be replaced with $B \rightarrow bA \rightarrow \epsilon$).

EDIT : As @rici said, if we apply subset construction to the last automaton, we get this one : (without dead states)

enter image description here

So this is an automaton that matches with $G$.

Source Link
user80502
user80502

The single $a$ indicates that if we are in state $A$, and read $a$, we must go to an ending state, same with single $b$. If we follow that, we get this automaton :

enter image description here

If we were less prudent, we would argue that if we can generate an $a$ with variable $A$ and stop, and because $A$ is an ending state, then we can put a loop on state $A$ labeled with $a$, like this :

enter image description here

But this automaton doesn't match with grammar $G$. This one recognize strings of the form $a^i$, but grammar $G$ can't generate them.

But something that can be done to lighten our automaton would be to remove state $B_f$, and count on our ending state $A$ to handle the case where we end generation with a single $b$, like the following :

enter image description here

And that actually correct, because we have : empty word on variable $A$, and a rule $B \rightarrow bA$ (In fact, we can remove from $G$ the rule $B \rightarrow b$, because it can be replaced with $B \rightarrow bA \rightarrow \epsilon$).

Finally, can we do the same with $A_f$ ? That is, remove it and put $B$ as an ending state, like the following :

enter image description here

Unfortunately, we can't to that, because we can't end on variable $B$ with empty word. So the correct automaton is the penultimate.