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

#1 iburres  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • 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  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 353
  • View blog
  • Posts: 774
  • 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

Was This Post Helpful? 0
  • +
  • -

#3 iburres  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • 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?
Was This Post Helpful? 0
  • +
  • -

#4 iburres  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • 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
	        


Was This Post Helpful? 0
  • +
  • -

#5 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 353
  • View blog
  • Posts: 774
  • 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

Was This Post Helpful? 2
  • +
  • -

#6 iburres  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • 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
Was This Post Helpful? 0
  • +
  • -

#7 iburres  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • 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


Was This Post Helpful? 0
  • +
  • -

#8 iburres  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#9 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 353
  • View blog
  • Posts: 774
  • 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

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1