1
$\begingroup$

I'm looking for hints on the following exercise from Introduction to Automata Theory, Languages and Computation by Hopcroft and Ullman.

Let $G$ be a grammar where all the productions are of the form $A\to xB$ and $A\to x$, where $A$ and $B$ are single variables and $x$ is a string of terminals. Show that $L(G)$ can be generated by a regular grammar.

This is from the second chapter of the book, so the solution should just require grammars (automata don't appear until chapter 3).

I assume that "Show that $L(G)$ can be generated by a regular grammar" means that I have to show the language generated, since this can be shown as regular grammar just by pointing out the productions.

This is where I get a bit confused...

Edit: Wrong usage of production so this is wrong, therefore what i did below is the wrong way to tackle this exercise

If i start doing the productions: \begin{align*} A&\to xB\\ \text{(with second)} A&\to AB\\ \text{(with first)} A&\to xBB \end{align*} And so on... so in the (n)th step $A^* → x^{n-1}B^n$ Since There would always be one $B$ more than $x$.

I was thinking that maybe I could change $xB$ for $A$ then for $x$ again to have just the string of terminals $x$ resulting in what the language generates, and this is where I think I am probably not understanding something right. I assume I am wrong because there cant be a non terminal when generating a Language...Right? Or am I just doing it all wrong?

Thank you for your time. I'm learning in Japan and my professor's English isn't very good so I can't ask him.

Improve this question
$\endgroup$
6
  • $\begingroup$ Where are you getting $A\to AB$ from? Every rule in the grammar either turns a nonterminal into a terminal or a terminal and a nonterminal. You start with a single nonterminal, and no rule has more nonterminals on the right than the left, so the number of nonterminals can never increase. You start with one of them, so you must always have either one or none. $\endgroup$
    – David Richerby
    Apr 22, 2017 at 10:24
  • $\begingroup$ I thought that the only way to start generating would be changing the $x$ from $A\to xB$ for $A$ since $A\to x$. But I admit, this is the part I am not completely sure of what to do... How to deal with the non terminal $B$, I can't generate a Language with it. $\endgroup$
    – J. Roki
    Apr 22, 2017 at 10:50
  • $\begingroup$ OK. You need to go back and read the basic definitions of grammars. The rule "$A\to xB$" means "If you see an $A$, you're allowed to replace it with $xB$." $\endgroup$
    – David Richerby
    Apr 22, 2017 at 11:04
  • $\begingroup$ Ok I understand why what I did is not right. $\endgroup$
    – J. Roki
    Apr 22, 2017 at 11:42
  • $\begingroup$ @DavidRicherby Do you know of any place (internet) I can find some exercise and the way to solve them (like, showing the steps even if a little), I don't have much references right now but simple examples and most of the things I find related to the topic are people using Automatas to solve exercises. $\endgroup$
    – J. Roki
    Apr 23, 2017 at 1:30

1 Answer 1

Reset to default
2
$\begingroup$

The only thing that prevents your grammar from being a regular grammar is that $x$ is a string rather than a single terminal. That means that you have to deal with two kinds of problems:

  1. $x$ is a string containing more than one terminal.
  2. $x$ is the empty string.

To deal with the first problem, replace each problematic rule by a chain of equivalent rules of the proper form. For example, $A \to \alpha \beta$ is the same as $A \to \alpha X$ and $X \to \beta$.

To deal with the second problem, you have to get rid of rules of the form $A\to B$ and of rules of the form $A \to \epsilon$. Hopefully this is something you already know how to do. If not, notice that $A \to B$ means that whenever you have $A$, you can replace it with $B$, and $A \to \epsilon$ means that whenever you have $A$, you can remove it. Doing so recursively will allow you to get rid of these rules.

Improve this answer
$\endgroup$
11
  • $\begingroup$ Ah! ok, yeah it has to be a single terminal for it to be regular (I had in my mind it could be many terminals for some reason). Thank you I will try to deal with those 2 problems then. If I do, I could justify that L(G) is generated by a regular grammar because I proved that G is a regular grammar, right? $\endgroup$
    – J. Roki
    Apr 22, 2017 at 11:38
  • $\begingroup$ The original grammar isn't necessarily regular. $\endgroup$
    – Yuval Filmus
    Apr 22, 2017 at 11:40
  • 1
    $\begingroup$ To show that $L(G)$ can be generated by a regular grammar, you need to prove that some regular grammar $H$ satisfies $L(H) = L(G)$. The simplest way to do so is to explicitly construct $H$. $\endgroup$
    – Yuval Filmus
    Apr 22, 2017 at 12:32
  • 1
    $\begingroup$ I think your current level of comprehension of the material isn't sufficient for solving (or even understanding) this exercise. I suggest contacting a TA, or waiting until the end of the course before you get back to this exercise. $\endgroup$
    – Yuval Filmus
    Apr 22, 2017 at 15:11
  • 1
    $\begingroup$ The question is your mathematical maturity, not your position in the textbook. Hopefully your mathematical maturity will increase as you read more and solve more exercises. $\endgroup$
    – Yuval Filmus
    Apr 22, 2017 at 15:15

Your Answer

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

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