Which type of formal language can be generated by a context-free grammar, where the left-hand side of every production rule consists of a single non-terminal symbol?

Which type of formal language can be generated by a context-free grammar, where the left-hand side of every production rule consists of a single non-terminal symbol?

• A. Context-Free Language
• B. Regular Language
• C. Context-Sensitive Language
• D. Unrestricted Language

Answer: (A)

The left-hand side being a single non-terminal is the defining feature of a context-free grammar. In such grammars, each production rewrites one non-terminal into a string of terminals and/or non-terminals, regardless of the surrounding context. The languages produced by these grammars are called context-free languages. While all regular languages are also context-free (since they can be described by a CFG that is restricted to be right- or left-linear), CFGs in general can generate more complex structures, so the appropriate category here is context-free language.

The left-hand side being a single non-terminal is the defining feature of a context-free grammar. In such grammars, each production rewrites one non-terminal into a string of terminals and/or non-terminals, regardless of the surrounding context. The languages produced by these grammars are called context-free languages. While all regular languages are also context-free (since they can be described by a CFG that is restricted to be right- or left-linear), CFGs in general can generate more complex structures, so the appropriate category here is context-free language.