MHB How to find a language generated by a given grammar

[evinda]

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> I | \varnothing \}</i> ,where I is the start symbol, how can I find the language?

 

[Evgeny.Makarov]

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]

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]

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]

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]

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]

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]

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()
\]

 

[evinda]

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?