Question

A difference between finite automata and context-free grammars is:

(a) A finite automaton must have a unique start state and a context-free grammar may have multiple start variables.
(b) A finite automaton cannot accept the language of strings that have an equal number of 0s and 1s and a context-free grammar can generate that language.
(c) A finite automaton has a finite language and a context-free grammar may have may have an infinite language.
(d) No state in a finite automaton can have multiple arcs leaving it with the same input symbol, and a contextfree grammar may have may have multiple production rules with the same terminal symbol as the first symbol on the right-hand side.

Answer 1

The correct difference is option (b), as finite automata cannot recognize the language of strings with an equal number of 0s and 1s, while context-free grammars can indeed generate such a language.

Step-by-step explanation:

The difference between finite automata and context-free grammars in the options provided is a finite automaton cannot accept the language of strings that have an equal number of 0s and 1s and a context-free grammar can generate that language.

Finite automata are state machines with a finite number of states used for recognizing regular languages, while context-free grammars consist of production rules that are used to generate context-free languages. A finite automaton does have a unique start state but can produce an infinite language given a loop in the automaton, therefore, option (c) is incorrect as both finite automata and context-free grammars can describe infinite languages.

The statement in option (d) is incorrect because a finite automaton can have multiple transitions from the same state with the same input symbol. However, deterministic finite automata (DFA), a subtype of finite automata, do indeed have only one transition per symbol from each state.