Theory of Computation20815 marksEquivalence of regular grammar and finite automata
Represent the following regular grammar to finite automata. S→aA∣aB∣εS \rightarrow aA \mid aB \mid \varepsilonS→aA∣aB∣εA→aA∣aSA \rightarrow aA \mid aSA→aA∣aSB→bB∣εB \rightarrow bB \mid \varepsilonB→bB∣ε
Represent the following regular grammar to finite automata. S→aA∣aB∣εS \rightarrow aA \mid aB \mid \varepsilonS→aA∣aB∣εA→aA∣aSA \rightarrow aA \mid aSA→aA∣aSB→bB∣εB \rightarrow bB \mid \varepsilonB→bB∣ε[5]
Production Rules ------ S → aA \ aB \ ε A → aA \ aS B → bB \ ε --- Each non-terminal in the grammar becomes a state in the FA. We also need a dead/final state for terminals. - States: S, A, B, F (where F is the final/accepting state) - S is the start state - Since S → ε and B → ε, both S and B ar...