Recent questions tagged ambiguous

0 votes

0 answers

1

Michael Sipser Edition 3 Exercise 2 Question 51 (Page No. 159)
Show that every DCFG is an unambiguous CFG.

asked Oct 13, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.7k points) | 6 views

0 votes

0 answers

2

Michael Sipser Edition 3 Exercise 2 Question 46 (Page No. 158)
Consider the following CFG $G:$ $S \rightarrow SS \mid T$ $T \rightarrow aT b \mid ab$ Describe $L(G)$ and show that $G$ is ambiguous. Give an unambiguous grammar $H$ where $L(H) = L(G)$ and sketch a proof that $H$ is unambiguous.

asked Oct 12, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.7k points) | 12 views

0 votes

0 answers

3

Ullman (Compiler Design) Edition 2 Exercise 4.8 Question 1 (Page No. 285 - 286)
The following is an ambiguous grammar for expressions with $n$ binary, infix operators, at $n$ ... ambiguous and unambiguous) grammars compare? What does that comparison tell you about the use of ambiguous expression grammars?

asked Aug 20, 2019 in Compiler Design by Lakshman Patel RJIT Veteran (58.7k points) | 11 views

0 votes

0 answers

4

Ullman (Compiler Design) Edition 2 Exercise 4.3 Question 3 (Page No. 217)
The following grammar is proposed to remove the "danglingelse ambiguity" discussed in Section $4.3.2$: $stmt\rightarrow if\: expr\: then\: stmt\mid matchedstmt$ $matchedstmt \rightarrow if \:expr \:then \:matchedstmt\: else\: stmt\mid other$ Show that this grammar is still ambiguous.

asked Aug 20, 2019 in Compiler Design by Lakshman Patel RJIT Veteran (58.7k points) | 17 views

+1 vote

0 answers

5

Ullman (Compiler Design) Edition 2 Exercise 4.2 Question 2 (Page No. 206 - 207)
Repeat Question $4.2.1$ for each of the following grammars and strings: $S\rightarrow 0S1\mid 01$ with string $000111$. $S\rightarrow +SS\mid \ast SS\mid a$ with string $+\ast aaa$ ... $bfactor\:\rightarrow\:not\:bfactor\mid (bexpr)\mid true\mid false$

asked Aug 17, 2019 in Compiler Design by Lakshman Patel RJIT Veteran (58.7k points) | 13 views

0 votes

1 answer

6

Ullman (Compiler Design) Edition 2 Exercise 4.2 Question 1 (Page No. 206)
Consider the context-free grammar:$S\rightarrow SS + \mid SS {\ast} \mid a$and the string $aa + a{\ast}$. Give a leftmost derivation for the string. Give a rightmost derivation for the string. ... for the string. Is the grammar ambiguous or unambiguous? Justify your answer. Describe the language generated by this grammar.

asked Aug 7, 2019 in Compiler Design by Lakshman Patel RJIT Veteran (58.7k points) | 51 views

+1 vote

2 answers

7

Ullman (Compiler Design) Edition 2 Exercise 2.2 Question 3 (Page No. 51)
Which of the grammars are ambiguous? $S\rightarrow 0S1 \mid 01$ $S\rightarrow +SS \mid -SS \mid a$ $S\rightarrow S(S)S \mid \epsilon$ $S\rightarrow aSbS \mid bSaS \mid \epsilon$ $S\rightarrow a \mid S+S \mid SS \mid S^{\ast} \mid (S)$

asked Jul 26, 2019 in Compiler Design by Lakshman Patel RJIT Veteran (58.7k points) | 25 views

+1 vote

0 answers

8

Self Doubt : Ambiguity
Why is ambiguity in regular language is decidable and not decidable in CFL ? Can you give Example?

asked May 10, 2019 in Theory of Computation by logan1x Active (1.1k points) | 135 views

0 votes

1 answer

9

Michael Sipser Edition 3 Exercise 2 Question 9 (Page No. 155)
Give a context-free grammar that generates the language $A=\{a^{i}b^{j}c^{k}\mid i=j$ $\text{or}$ $ j=k$ $\text{where}$ $ i,j,k\geq 0\}.$ Is your grammar ambiguous$?$ Why or why not$?$

asked May 1, 2019 in Theory of Computation by Lakshman Patel RJIT Veteran (58.7k points) | 18 views

0 votes

0 answers

10

Peter Linz Edition 4 Exercise 5.2 Question 19 (Page No. 145)
Prove the following result. Let $G = (V, T, S, P )$ be a context-free grammar in which every $A ∈ V$ occurs on the left side of at most one production. Then $G$ is unambiguous.

asked Apr 14, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 15 views

0 votes

0 answers

11

Peter Linz Edition 4 Exercise 5.2 Question 18 (Page No. 145)
Is the string $aabbababb$ in the language generated by the grammar $S → aSS|b$? Show that the grammar with productions $S\rightarrow aAb|\lambda,$ $A\rightarrow aAb|\lambda$ is unambiguous.

asked Apr 14, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 20 views

0 votes

0 answers

12

Peter Linz Edition 4 Exercise 5.2 Question 16 (Page No. 145)
Show that the grammar with productions $S\rightarrow aAB,$ $A\rightarrow bBb,$ $B\rightarrow A|\lambda.$ is unambiguous.

asked Apr 14, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 24 views

0 votes

0 answers

13

Peter Linz Edition 4 Exercise 5.2 Question 15 (Page No. 145)
Show that the grammar with productions $S\rightarrow SS,$ $S\rightarrow \lambda,$ $S\rightarrow aSb,$ $S\rightarrow bSa.$ is ambiguous.

asked Apr 14, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 34 views

0 votes

0 answers

14

Peter Linz Edition 4 Exercise 5.2 Question 14 (Page No. 145)
Show that the grammar $S\rightarrow aSb|SS|\lambda$ is ambiguous, but that the language denoted by it is not.

asked Apr 14, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 17 views

0 votes

0 answers

15

Peter Linz Edition 4 Exercise 5.2 Question 13 (Page No. 145)
Show that the following grammar is ambiguous. $S\rightarrow aSbS|bSaS|\lambda$

asked Apr 14, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 16 views

0 votes

0 answers

16

Peter Linz Edition 4 Exercise 5.2 Question 11 (Page No. 145)
Is it possible for a regular grammar to be ambiguous?

asked Apr 14, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 14 views

0 votes

0 answers

17

Peter Linz Edition 4 Exercise 5.2 Question 7 (Page No. 145)
Construct an unambiguous grammar equivalent to the grammar in Exercise 6.

asked Apr 14, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 18 views

0 votes

0 answers

18

Peter Linz Edition 4 Exercise 5.2 Question 6 (Page No. 145)
Show that the following grammar is ambiguous. $S\rightarrow AB|aaB,$ $A\rightarrow a|Aa,$ $B\rightarrow b.$

asked Apr 14, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 14 views

0 votes

0 answers

19

Peter Linz Edition 4 Exercise 5.2 Question 4 (Page No. 145)
Show that every s-grammar is unambiguous.

asked Apr 14, 2019 in Theory of Computation by Naveen Kumar 3 Boss (15.4k points) | 8 views

0 votes

0 answers

20

DFA NFA and ambiguity
Why is Regular grammar obtained from DFA always unambiguous? Why Regular grammar obtained from NFA may or may not be ambiguous?

asked Dec 7, 2018 in Theory of Computation by OneZero Active (2.1k points) | 62 views

0 votes

1 answer

21

Doubt in Grammar
Consider the following grammar which of the following is/are ambiguous? (i) S → y | SxS (ii) S → E | ExS and E → y (iii) S → Sxy | y

asked Sep 11, 2018 in Theory of Computation by goluabhinan (71 points) | 55 views

0 votes

0 answers

22

UGC NET DEC 2017 PAPER 2 Q 34-
Which of the following statements is/are TRUE ? (i) The grammar S → SS | a is ambiguous (where S is the start symbol). (ii) The grammar S → 0S1 | 01S | e is ambiguous (the special symbol e represents the empty string and S is the start symbol). (iii) The grammar ... TRUE (D) All of (i), (ii) and (iii) are TRUE Sure shot (i) and (ii) are true i want third one in brief

asked Jun 19, 2018 in Compiler Design by Nikhil Patil Junior (505 points) | 292 views

0 votes

0 answers

23

Compiler design
Hi mates, Show that it is ambiguous grammar TIA S->aAB/bBA A->bS/a B->aS/b

asked Nov 24, 2017 in Compiler Design by Sahil1994 Junior (951 points) | 74 views

+1 vote

1 answer

24

UGCNET-Nov2017-ii-34
Which of the following statements is/are TRUE ? (a) The grammar $S \rightarrow SS\ |\ a$ is ambiguous. (Where $S$ is the start symbol) (b) The grammar $S \rightarrow 0S1\ |\ 01S\ |\ \epsilon$ is ambiguous. (The special symbol $\epsilon$ represents the empty string) (Where $S$ is the ... and (c) are TRUE. $(3)$ Only (b) and (c) are TRUE. $(4)$ All of (a), (b) and (c) are TRUE.

asked Nov 5, 2017 in Theory of Computation by Arjun Veteran (430k points) | 1.1k views

0 votes

0 answers

25

Ambiguity
Ques. S --> Aa/bAc/dc A --> d Isn't this grammar Ambiguous? If First(S) has more than one production giving the same first value, isn't it ambiguous?

asked Aug 22, 2017 in Compiler Design by Warlock lord Active (3.3k points) | 87 views

+2 votes

1 answer

26

REGULAR OR NOT
As given that 1st is not regular and 2nd is regular as 1st not form AP but 2nd form.but if in 2nd we fix value of m and n same then it will work as 1st(not regular) so 2nd also should not be regular.as i know if we fix m or n value as any constant it will be AP but what if same???

asked Aug 8, 2017 in Theory of Computation by learner_geek Active (3.3k points) | 249 views

+2 votes

1 answer

27

REGULAR OR NOT
Please mention reason with answer:-

asked Aug 8, 2017 in Theory of Computation by learner_geek Active (3.3k points) | 92 views

0 votes

1 answer

28

TestBook TestSeries
Consider the following statements : i) An ambiguous grammar can not generate DCFL. ii) An unambiguous grammar will always generate deterministic context free language. iii) Any non-empty language admits an ambiguous grammar. iv) All regular grammars are unambiguous. Which of the above is/are TRUE? i) and iv) only ii) and iii) only iii) only ii) and iv) only

asked Jan 29, 2017 in Theory of Computation by vnc Active (2.9k points) | 95 views

0 votes

0 answers

29

Self Doubt
By seeing a grammar I can say it is ambiguous or not. But How can I say it is inherently ambiguous or not.?

asked Jan 22, 2017 in Theory of Computation by Lucky sunda Active (4.5k points) | 140 views

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true

Recent questions tagged ambiguous

Recent Posts

Recent Blog Comments