I am having trouble determining the language from a given context free grammar. I've been given a hint that there are 2 parts to the language but can't figure either out.

$$G= (\{S,A,B,C,D,E,Z\},(0,1),R,S),$$

$\quad S\to E\mid Z$
$\quad E\to A\mid C $
$\quad A\to 01B\mid 0A\mid\epsilon$
$\quad B\to 1B\mid 10A $
$\quad C\to 10D\mid 1C\mid\epsilon$
$\quad D\to 01C\mid 0D $
$\quad Z\to 0Z1\mid e$

I have figured out $Z$ always produces a string with an equal number of 0s and 1s.

  • 1
    $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Feb 21 '19 at 5:27
  • 1
    $\begingroup$ Try proving your guess correct and observe where it fails. Continue from there. $\endgroup$ – Raphael Feb 21 '19 at 5:28
  • $\begingroup$ @Apass.Jack the question on my hw gives a hint that there are 2 parts to it $\endgroup$ – jordan neely Feb 21 '19 at 6:21
  • $\begingroup$ "Do you know which 2 parts that are represented by which non-terminals?" "Please show your understanding in the question." Have you found at least one part? $\endgroup$ – John L. Feb 21 '19 at 6:23
  • 1
    $\begingroup$ @Apass.Jack Thats makes sense. So if it is Z the number of 0s and 1s are equal right? $\endgroup$ – jordan neely Feb 21 '19 at 6:31

A basic way to understand the language generated by a formal grammar is to understand the grammar, part by part.

In particular, for a context-free grammar, each non-terminal can be treated as the starting non-terminal and, hence, can be used to derive a context-free language. For example, starting from $Z$, we have only one rule, $Z\to 0Z1\mid\epsilon$. As you have found, $Z$ represents $L_Z$, the language of words of zero or more number of 0's followed by the same number of 1's.

$S\to E\mid Z$ means $L_S=L_E\cup L_Z$. What is nice about this union? The set of production rules starting from $E$ is disjoint from the set of production rules starting from $Z$. So we can analyze $L_E$ and $L_Z$ separately.

What is $L_E$? $E\to A\mid C$ means $L_E=L_A\cup L_C$.

What is $L_A$? Here are the rules that starting from $A$.
$\quad A\to 01B\mid 0A\mid\epsilon$
$\quad B\to 1B\mid 10A$

You are supposed to play with these two rules for a while. What are the words in $L_A$? Here are some of them. $\epsilon$, 0, 00, 000, 0110, 0000, 01110, 00110, 01100, 00000, 0001 10, 011100, 001110, 001100, 011110, 011000, 0110000, 0011000, 0111000, 01100110. If you have played that much, you will probably have a pretty good idea about the pattern.

Here is a way to see what is happening.

  • $A$ can be empty word because of the rule $A\to\epsilon$.
  • We can add one or more 0's before $A$ because of rule $A\to 0A$.
  • From $A$, we can add 10 before it, turning it into $B$ because of rule $B\to 10A$. Then we can add zero or more 1's before that $B$, keeping it as a $B$ because of the rule $B\to 1B$. Then we can add 01 before it, turning it back into $A$.

We can repeat the process of turning $A$ to $A$ any number of times as well as finally turning $A$ to the empty word . So $L_A\supseteq(0+011^*10)^*$, which is, in fact, an equality. $L_A$ is the language of words without lonely 1's and with at least two 0's between any two groups of 1's which start and end with 0 except the empty word.

The above method seems ad-hoc. That is something that should be done whenever there is time to playing with rules and observing patterns.

Another approach is to observe the rules starting from $A$ have only one terminal on the right hand side. Furthermore, that one terminal only appears once and at the end. That means the grammars for $A$ is an extended right regular grammar. "There is a direct one-to-one correspondence between the rules of a (strictly) right regular grammar and those of a nondeterministic finite automaton, such that the grammar generates exactly the language the automaton accepts". I will encourage you to explore that correspondence. There are systemic ways to compute regular expressions from NFA.

The above should give you enough hint and direction to complete the rest of the task such as figuring out what is $L_C$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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