1
$\begingroup$

In the definition of unrestricted (type 0) grammars we only really have the rule that the lhs cannot be the empty string.

Then, is it allowed to have a production rule with an lhs consisting only of terminal symbols? And if yes, is it correct to say that such production rule cannot be applied, since it does not contain non-terminal symbols?

$\endgroup$
2
  • 1
    $\begingroup$ This is an arbitrary decision that has no effect on the expressive power of unrestricted grammars. Check the details of whatever exact definition you are using to see if it conforms to the definition. $\endgroup$ Nov 26, 2022 at 10:14
  • $\begingroup$ I think a good follow up question is: what's the difference between terminals and non-terminals in that case? $\endgroup$
    – Alexey
    Jan 30, 2023 at 17:24

1 Answer 1

2
$\begingroup$

No, an unrestricted grammar cannot have a rule with only terminals on the left-hand side. In formal grammar, a production rule is written in the form of:

α → β

where α and β are strings of symbols, and α contains at least one nonterminal symbol. By definition, an unrestricted grammar (also known as a Type 0 grammar) has no constraints on the form of its production rules except for this basic requirement.

Terminal symbols are the basic symbols in a language, from which the language's strings are constructed. In contrast, nonterminal symbols are used to define the structure of the language and are replaced by other symbols (both terminal and nonterminal) during the derivation process.

If a rule has only terminals on the left-hand side, it would violate the fundamental requirement for at least one nonterminal symbol in α. Such a rule would not make sense in the context of formal grammars, as there would be no way to replace the terminal symbols on the left-hand side and derive strings from them.

References:

  1. Chomsky, N. (1956). Three models for the description of language. IRE Transactions on information theory, 2(3), 113-124.
  2. Hopcroft, J. E., Motwani, R., & Ullman, J. D. (2006). Introduction to automata theory, languages, and computation (3rd ed.). Pearson/Addison-Wesley.
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.