1

I have to create the syntax tree for the word (())()() . That's what I have tried: enter image description here

Could you tell me if it is right?

evinda
  • 7,823
  • 1
    Can we know the grammar you used? – hhsaffar Dec 21 '13 at 21:30
  • The grammar is context-free.. – evinda Dec 21 '13 at 21:42
  • 1
    @evinda Without the specific grammar, there's no way for us to know if the parse tree you gave is correct for that grammar. Often the grammar for strings of balanced parentheses is given as $$\begin{align}S &\to \epsilon \mid (S)S \end{align};$$ or sometimes $$ \begin{align}S &\to \epsilon \mid SS \mid (S); \end{align}$$ if either of those is your grammar, then your parse tree is wrong. But it's possible you are working from some different grammar for which your parse tree is correct. There's no way for us to know unless you tell us. – MJD Dec 21 '13 at 21:45
  • I have to use the following grammar: Σ={(,)} ,
    Σ$_{Q}$={I} ,
    initial : I ,
    δ={I->(I)I|0} ,where 0 the empty set.     – evinda Dec 21 '13 at 21:57
  • Or don't you mean this? – evinda Dec 21 '13 at 23:54

2 Answers2

3

$\def\lp{{\mathtt (}}\def\rp{{\mathtt )}}$ You said in a comment that you are using this grammar:

$$\begin{align} I \to & \lp I\rp I \\ \mid & 0 \end{align}$$ where $0$ represents the empty sequence of symbols.

In that case your tree is not correct. The leftmost $I$ node in the second level of your tree has only three children, but it must have four or none.

The fix for this problem is pretty simple. Instead of having $I\to\lp I \rp$ as it is now, give the node four children, $I\to\lp I \rp I$, and then have the fourth one turn into nothing using the $I\to 0$ production.

Another problem is that your root node $I$ has five children, labeled with (, $I$, ), $I$, and $I$, but the only legal productions from $I$ have either four children (the $I\to\lp I\rp I$ production) or none (the $I\to 0$ peoduction).

The fix for this is a little more complicated and I don't want to lead you to possibly violate your school's ethics code by telling you what is it.

Finally, you have an inconsistency: Sometimes you have an $I$ node turn into $0$ using the $I\to 0$ production, and sometimes you just leave the $I$ as a leaf. You need to make up your mind how you want to draw the $I\to 0$ production, and then draw it that way consistently.

MJD
  • 65,394
  • 39
  • 298
  • 580
0

@MJD I tried to create again the syntax tree..That's what I got.Have I done something wrong or is this right? enter image description here

evinda
  • 7,823
  • 1
    That looks better, except that you have a node $I$ over on the lower right that has one child, also labeled $I$. There is no production $I\to I$, so that's not allowed. But you can easily delete the extra $I$ and move its children up, and your answer will be correct. – MJD Dec 24 '13 at 23:50
  • 1
    @MJD Thank you very much!And merry Christmas!! – evinda Dec 25 '13 at 13:12