Dark Mode

Recent questions tagged ambiguous

1 vote

2 answers

1

can someone share the approach for the following que
14.Show that the grammar S → aSb |SS| e is ambiguous, but that the language denoted by it is not. Can someone share the approach for second part.

mk_007 asked in Theory of Computation Oct 3, 2021

by mk_007

165 views

0 votes

2 answers

2

UGC NET CSE | October 2020 | Part 2 | Question: 57
Which of the following grammars is(are) ambiguous? $s \rightarrow ss \mid asb \mid bsa \mid \lambda$ $s \rightarrow asbs \mid bsas \mid \lambda$ ... below: $(a)$ and $(c)$ only $(b)$ only $(b)$ and $(c)$ only $(a)$ and $(b)$ only

go_editor asked in Theory of Computation Nov 20, 2020

1.5k views

0 votes

1 answer

3

NIELIT 2017 DEC Scientist B - Section B: 26
The grammar $S\rightarrow aSb\mid bSa\mid SS\mid \varepsilon $ is: Unambiguous CFG Ambiguous CFG Not a CFG Deterministic CFG

Lakshman Patel RJIT asked in Compiler Design Mar 30, 2020

by Lakshman Patel RJIT

866 views

0 votes

0 answers

4

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

Lakshman Patel RJIT asked in Theory of Computation Oct 13, 2019

by Lakshman Patel RJIT

157 views

0 votes

0 answers

5

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.

Lakshman Patel RJIT asked in Theory of Computation Oct 12, 2019

by Lakshman Patel RJIT

335 views

0 votes

0 answers

6

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?

Lakshman Patel RJIT asked in Compiler Design Aug 20, 2019

by Lakshman Patel RJIT

544 views

0 votes

0 answers

7

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.

Lakshman Patel RJIT asked in Compiler Design Aug 20, 2019

by Lakshman Patel RJIT

402 views

1 vote

0 answers

8

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$

Lakshman Patel RJIT asked in Compiler Design Aug 17, 2019

by Lakshman Patel RJIT

516 views

3 votes

1 answer

9

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.

Lakshman Patel RJIT asked in Compiler Design Aug 7, 2019

by Lakshman Patel RJIT

6.1k views

1 vote

2 answers

10

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)$

Lakshman Patel RJIT asked in Compiler Design Jul 26, 2019

by Lakshman Patel RJIT

946 views

3 votes

1 answer

11

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

logan1x asked in Theory of Computation May 10, 2019

709 views

0 votes

1 answer

12

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$?$

Lakshman Patel RJIT asked in Theory of Computation May 1, 2019

by Lakshman Patel RJIT

325 views

0 votes

0 answers

13

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.

Naveen Kumar 3 asked in Theory of Computation Apr 14, 2019

by Naveen Kumar 3

133 views

0 votes

1 answer

14

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.

Naveen Kumar 3 asked in Theory of Computation Apr 14, 2019

by Naveen Kumar 3

230 views

0 votes

0 answers

15

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.

Naveen Kumar 3 asked in Theory of Computation Apr 14, 2019

by Naveen Kumar 3

202 views

0 votes

1 answer

16

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.

Naveen Kumar 3 asked in Theory of Computation Apr 14, 2019

by Naveen Kumar 3

237 views

0 votes

1 answer

17

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.

Naveen Kumar 3 asked in Theory of Computation Apr 14, 2019

by Naveen Kumar 3

193 views

0 votes

1 answer

18

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

Naveen Kumar 3 asked in Theory of Computation Apr 14, 2019

by Naveen Kumar 3

150 views

0 votes

0 answers

19

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

Naveen Kumar 3 asked in Theory of Computation Apr 14, 2019

by Naveen Kumar 3

105 views

0 votes

1 answer

20

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

Naveen Kumar 3 asked in Theory of Computation Apr 14, 2019

by Naveen Kumar 3

161 views

1 vote

1 answer

21

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.$

Naveen Kumar 3 asked in Theory of Computation Apr 14, 2019

by Naveen Kumar 3

160 views

0 votes

0 answers

22

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

Naveen Kumar 3 asked in Theory of Computation Apr 14, 2019

by Naveen Kumar 3

141 views

0 votes

0 answers

23

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?

OneZero asked in Theory of Computation Dec 7, 2018

437 views

0 votes

1 answer

24

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

goluabhinan asked in Theory of Computation Sep 11, 2018

1.0k views

0 votes

2 answers

25

Compiler design

Deepalitrapti asked in Compiler Design Jul 19, 2018

by Deepalitrapti

157 views

1 vote

1 answer

26

gate forum test series
Why option B is wrong?? can someone help.....

himanshu19 asked in Theory of Computation Dec 23, 2017

131 views

0 votes

0 answers

27

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

Sahil1994 asked in Compiler Design Nov 24, 2017

180 views

1 vote

1 answer

28

UGC NET CSE | November 2017 | Part 2 | Question: 34
Which of the following statements is/are TRUE? The grammar $S \rightarrow SS \mid a$ is ambiguous. (Where $S$ is the start symbol) The grammar $S \rightarrow 0S1 \mid 01S \mid \epsilon$ is ambiguous. (The special symbol $\epsilon$ represents the empty string) ( ... a) and (c) are TRUE. Only (b) and (c) are TRUE. All of (a), (b) and (c) are TRUE.

Arjun asked in Theory of Computation Nov 5, 2017

by Arjun

3.5k views

0 votes

0 answers

29

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?

Warlock lord asked in Compiler Design Aug 22, 2017

by Warlock lord

599 views

2 votes

1 answer

30

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???

learner_geek asked in Theory of Computation Aug 8, 2017

by learner_geek

395 views

Page:

Recent questions tagged ambiguous