# Ambiguous Grammar

Page 1 of 1

## 8 Replies - 1774 Views - Last Post: 02 October 2013 - 08:54 AM

### #1 iburres

Reputation: 0
• Posts: 148
• Joined: 05-September 12

# Ambiguous Grammar

Posted 01 October 2013 - 12:41 PM

I couldn't find a computer science forum, so I figured this was the next best place.

Given this grammar:

S → SA | AS | A
A → 0 | 1

What is an example of a sentential form that would have two different parse trees (and therefore be ambiguous)? Would I use something like SA + AS * A or should I be using A = 1 + 1 * 0? And then construct my two parse trees.
Is This A Good Question/Topic? 0

## Replies To: Ambiguous Grammar

### #2 mojo666

Reputation: 352
• Posts: 771
• Joined: 27-June 09

## Re: Ambiguous Grammar

Posted 01 October 2013 - 01:22 PM

I think you just need a string of 1's and 0's that could be produced by multiple parse trees. It seems pretty trivial to do with the given grammar.

EDIT: Just looked up "sentential form". In this case, it can be any string of S's, A's, 1's, and 0's that can be produced by the grammar.

This post has been edited by mojo666: 01 October 2013 - 01:27 PM

### #3 iburres

Reputation: 0
• Posts: 148
• Joined: 05-September 12

## Re: Ambiguous Grammar

Posted 01 October 2013 - 01:36 PM

Got ya, but what's confusing me is the fact that S can be defined as either SA or AS or A. Am I supposed to treat SA as S * A and vice versa?

### #4 iburres

Reputation: 0
• Posts: 148
• Joined: 05-September 12

## Re: Ambiguous Grammar

Posted 01 October 2013 - 01:48 PM

Like this?

```

S

A

A	+	A

1	   A       *       A

1	          0

```

### #5 mojo666

Reputation: 352
• Posts: 771
• Joined: 27-June 09

## Re: Ambiguous Grammar

Posted 01 October 2013 - 01:54 PM

Quote

Am I supposed to treat SA as S * A and vice versa?

The grammar tells you how to treat SA. You treat it by replacing S with one of the 3 options given for S and replacing the A with one of the two options given for A. Then keep replacing the resulting choices until you are left with 0's and 1's.

Quote

Like this?

No. This would be an example to Parse "1" from the sentence. "1" is not ambiguous because there is only 1 way to get it

```S
A
1
```

This post has been edited by mojo666: 01 October 2013 - 02:03 PM

### #6 iburres

Reputation: 0
• Posts: 148
• Joined: 05-September 12

## Re: Ambiguous Grammar

Posted 01 October 2013 - 01:58 PM

Ahh that's my problem. DOPE!

Thank you very much

### #7 iburres

Reputation: 0
• Posts: 148
• Joined: 05-September 12

## Re: Ambiguous Grammar

Posted 01 October 2013 - 02:06 PM

Here is my solution for the string 1110:

```
S

A	    SA

1	 AS   0

1   A

1

```

### #8 iburres

Reputation: 0
• Posts: 148
• Joined: 05-September 12

## Re: Ambiguous Grammar

Posted 01 October 2013 - 02:18 PM

And if I flip the SA to AS I get a second parse tree with the same outcome. Thanks again.

### #9 mojo666

Reputation: 352
• Posts: 771
• Joined: 27-June 09

## Re: Ambiguous Grammar

Posted 02 October 2013 - 08:54 AM

Almost. You missed a step.
```
S

AS

1	    SA

AS    0

1    A

1

```

This post has been edited by mojo666: 02 October 2013 - 08:54 AM