How to find a language generated by a given grammar

evinda

Well-known member
MHB Site Helper
If I am given a grammar,how can I find which language it generates?For example,if I am given the following grammar:
{w $$\epsilon$$ {(,) [,]}$$^{*}$$:$$I\rightarrow(I)I | I | \varnothing \}$$ ,where I is the start symbol, how can I find the language?

Last edited by a moderator:

Evgeny.Makarov

Well-known member
MHB Math Scholar
Re: Find the context-free grammar,that produces a language

If I am given a grammar,how can I find which language it generates?
There is no general way. Try systematically drawing all possible derivations of length 0, 1, 2, ... until it is feasible. Looking at these examples may help you formulate a hypothesis about the language and later prove it. Try doing this for the language you gave.

evinda

Well-known member
MHB Site Helper
Re: Find the context-free grammar,that produces a language

There is no general way. Try systematically drawing all possible derivations of length 0, 1, 2, ... until it is feasible. Looking at these examples may help you formulate a hypothesis about the language and later prove it. Try doing this for the language you gave.
Isn't it like that:
-when length=0,the word is $$\varnothing$$
-when length=1, it is either () or []
-when length=2,it is ()[]
Or am I wrong?

Evgeny.Makarov

Well-known member
MHB Math Scholar
Re: Find the context-free grammar,that produces a language

The answer depends on how to count length. I'll assume it is the number of times any rule was applied.
Isn't it like that:
-when length=0,the word is $$\varnothing$$
If no rule was applied, we still have $I$.

-when length=1, it is either () or []
If you apply a rule just once and get a strings consisting of terminal symbols, it must be empty (the rule $I\to\varnothing$).

-when length=2,it is ()[]
Why do you think so?

evinda

Well-known member
MHB Site Helper
Re: Find the context-free grammar,that produces a language

The answer depends on how to count length. I'll assume it is the number of times any rule was applied.
If no rule was applied, we still have $I$.

If you apply a rule just once and get a strings consisting of terminal symbols, it must be empty (the rule $I\to\varnothing$).

Why do you think so?
Could you explain me why if we apply a rule just once, it must be empty (the rule $I\to\varnothing$) ? I haven't understood it

Also,how can I check,which is the word when we apply the rule 2 times??

Evgeny.Makarov

Well-known member
MHB Math Scholar
Re: Find the context-free grammar,that produces a language

Could you explain me why if we apply a rule just once, it must be empty (the rule $I\to\varnothing$) ?
This is true under the condition that the resulting string consists of terminal symbols. Why don't you try applying other rules just once to $I$ and see if you get a string consisting of all terminals?

Also,how can I check,which is the word when we apply the rule 2 times??
Look, there is a limit to what can be explained. I assume you know the definition of a grammar and how it generates words, i.e., how rules work. What kind of explanation do you need for this question? You check it by taking $I$ and then replacing it by the right-hand side of some rule. (Here all rules have left-hand side $I$, so they all apply.) For example, you get $(I)I$. Then again you pick one of the two $I$'s and replace it by the right-hand side of some rule. Please don't ask me to explain how to find $I$ in the string $(I)I$ and what it means to replace one substring by another.

Or are you confused by the form in which the rules are listed, using the vertical bar? The line
$I\rightarrow(I)I \mid I \mid \varnothing$
is an abbreviated way to write these three rules.
\begin{aligned} I&\rightarrow (I)I\\ I&\rightarrow I\\ I&\rightarrow \varnothing \end{aligned}

evinda

Well-known member
MHB Site Helper
Re: Find the context-free grammar,that produces a language

This is true under the condition that the resulting string consists of terminal symbols. Why don't you try applying other rules just once to $I$ and see if you get a string consisting of all terminals?

Look, there is a limit to what can be explained. I assume you know the definition of a grammar and how it generates words, i.e., how rules work. What kind of explanation do you need for this question? You check it by taking $I$ and then replacing it by the right-hand side of some rule. (Here all rules have left-hand side $I$, so they all apply.) For example, you get $(I)I$. Then again you pick one of the two $I$'s and replace it by the right-hand side of some rule. Please don't ask me to explain how to find $I$ in the string $(I)I$ and what it means to replace one substring by another.

Or are you confused by the form in which the rules are listed, using the vertical bar? The line
$I\rightarrow(I)I \mid I \mid \varnothing$
is an abbreviated way to write these three rules.
\begin{aligned} I&\rightarrow (I)I\\ I&\rightarrow I\\ I&\rightarrow \varnothing \end{aligned}

When we apply the rules,are some results these:[ ] , ( ) , [ ( ) ] , ( [ ] ) , [ ] ( ) , ( ) [ ] , ( [ ] ) ( ) [ ] ? Or am I wrong?

- - - Updated - - -

When we apply the rules,are some results these:[ ] , ( ) , [ ( ) ] , ( [ ] ) , [ ] ( ) , ( ) [ ] , ( [ ] ) ( ) [ ] ? Or am I wrong?
And if we apply the rule 2 times,is the result () or [] ?

Evgeny.Makarov

Well-known member
MHB Math Scholar
Re: Find the context-free grammar,that produces a language

When we apply the rules,are some results these:[ ] , ( ) , [ ( ) ] , ( [ ] ) , [ ] ( ) , ( ) [ ] , ( [ ] ) ( ) [ ] ?
This is much better. Yes, it is correct. We can proceed to start guessing the common property that these words satisfy. Both $I\to(I)I$ and $I\toI$ introduce opening and closing delimiters in pairs, so by induction every generated word has the same number of opening and closing parentheses, and the same for square brackets. But it seems that more is true: delimiters in every generated string are balanced. For example, in "())(" the number of opening and closing parentheses is the same, but parentheses are not balanced. Formally this means that every prefix of a balanced string has at least as many opening parentheses as closing ones. In contrast, the prefix "())" of "())(" has 1 opening parenthesis and two closing ones.

And if we apply the rule 2 times,is the result () or [] ?
The string "()" requires three rule applications:
$I\to (I)I\to()I\to()$

Last edited:

evinda

Well-known member
MHB Site Helper
Re: Find the context-free grammar,that produces a language

This is much better. Yes, it is correct. We can proceed to start guessing the common property that these words satisfy. Both $I\to(I)I$ and $I\toI$ introduce opening and closing delimiters in pairs, so by induction every generated word has the same number of opening and closing parentheses, and the same for square brackets. But it seems that more is true: delimiters in every generated string are balanced. For example, in "())(" the number of opening and closing parentheses is the same, but parentheses are not balanced. Formally this means that every prefix of a balanced string has at least as many opening parentheses as closing ones. In contrast, the prefix "())" of "())(" has 1 opening parenthesis and twp closing ones.

I understand!!!!

The string "()" requires three rule applications:
$I\to (I)I\to()I\to()$
So,applying two rules,is the result: $$I\to (I)I\to()I$$ ??Or not?