Recent questions tagged ambiguous / GATE Overflow for GATE CSE

0 votes

2 answers

1

Theory of Computation

gateexplore

256 views

gateexplore asked Jul 2, 2023

2 votes

0 answers

2

Can DCFL be ambiguous?
Can DCFL be ambiguous?

Can DCFL be ambiguous?

h4kr

464 views

h4kr asked Feb 2, 2023

1 votes

2 answers

3

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.

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

270 views

mk_007 asked Oct 2, 2021

1 votes

2 answers

4

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$ ... : $(i)$ and $(iii)$ only $(ii)$ only $(ii)$ and $(iii)$ only $(i)$ and $(ii)$ only

Which of the following grammars is(are) ambiguous?$s \rightarrow ss \mid asb \mid bsa \mid \lambda$$s \rightarrow asbs \mid bsas \mid \lambda$$s \rightarrow aAB \\ A \rig...

go_editor

2.2k views

go_editor asked Nov 20, 2020

0 votes

1 answer

5

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

The grammar $S\rightarrow aSb\mid bSa\mid SS\mid \varepsilon $ is:Unambiguous CFGAmbiguous CFGNot a CFGDeterministic CFG

admin

1.3k views

admin asked Mar 30, 2020

0 votes

0 answers

6

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

Show that every DCFG is an unambiguous CFG.

admin

227 views

admin asked Oct 12, 2019

0 votes

0 answers

7

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.

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

admin

422 views

admin asked Oct 12, 2019

0 votes

0 answers

8

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?

The following is an ambiguous grammar for expressions with $n$ binary, infix operators, at $n$ different levels of precedence: $E\rightarrow E\theta_{1}E\mid E\theta_{2}E...

admin

705 views

admin asked Aug 20, 2019

0 votes

0 answers

9

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.

The following grammar is proposed to remove the "danglingelse ambiguity" discussed in Section $4.3.2$:$stmt\rightarrow if\: expr\: then\: stmt\mid matchedstmt$$matchedst...

admin

606 views

admin asked Aug 20, 2019

1 votes

0 answers

10

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$

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

admin

748 views

admin asked Aug 17, 2019

4 votes

1 answer

11

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.

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

admin

10.8k views

admin asked Aug 7, 2019

1 votes

2 answers

12

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

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 \epsi...

admin

1.2k views

admin asked Jul 26, 2019

3 votes

1 answer

13

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

Why is ambiguity in regular language is decidable and not decidable in CFL ? Can you give Example?

logan1x

1.2k views

logan1x asked May 10, 2019

0 votes

1 answer

14

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

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

admin

558 views

admin asked May 1, 2019

0 votes

0 answers

15

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.

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

Naveen Kumar 3

211 views

Naveen Kumar 3 asked Apr 14, 2019

0 votes

1 answer

16

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.

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|\lambd...

Naveen Kumar 3

334 views

Naveen Kumar 3 asked Apr 14, 2019

0 votes

0 answers

17

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.

Show that the grammar with productions$S\rightarrow aAB,$$A\rightarrow bBb,$$B\rightarrow A|\lambda.$ is unambiguous.

Naveen Kumar 3

286 views

Naveen Kumar 3 asked Apr 14, 2019

0 votes

1 answer

18

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.

Show that the grammar with productions$S\rightarrow SS,$$S\rightarrow \lambda,$$S\rightarrow aSb,$$S\rightarrow bSa.$is ambiguous.

Naveen Kumar 3

338 views

Naveen Kumar 3 asked Apr 14, 2019

0 votes

1 answer

19

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.

Show that the grammar $S\rightarrow aSb|SS|\lambda$ is ambiguous, but that the language denoted by it is not.

Naveen Kumar 3

284 views

Naveen Kumar 3 asked Apr 14, 2019

0 votes

1 answer

20

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

Show that the following grammar is ambiguous. $S\rightarrow aSbS|bSaS|\lambda$

Naveen Kumar 3

224 views

Naveen Kumar 3 asked Apr 14, 2019

0 votes

0 answers

21

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

Is it possible for a regular grammar to be ambiguous?

Naveen Kumar 3

153 views

Naveen Kumar 3 asked Apr 14, 2019

0 votes

1 answer

22

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

Construct an unambiguous grammar equivalent to the grammar in Exercise 6.

Naveen Kumar 3

234 views

Naveen Kumar 3 asked Apr 14, 2019

1 votes

1 answer

23

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

Show that the following grammar is ambiguous.$S\rightarrow AB|aaB,$$A\rightarrow a|Aa,$$B\rightarrow b.$

Naveen Kumar 3

216 views

Naveen Kumar 3 asked Apr 14, 2019

0 votes

0 answers

24

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

Show that every s-grammar is unambiguous.

Naveen Kumar 3

205 views

Naveen Kumar 3 asked Apr 14, 2019

0 votes

0 answers

25

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?

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

OneZero

598 views

OneZero asked Dec 7, 2018

0 votes

1 answer

26

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

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

1.3k views

goluabhinan asked Sep 11, 2018

0 votes

2 answers

27

Compiler design

Deepalitrapti

309 views

Deepalitrapti asked Jul 19, 2018

1 votes

1 answer

28

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

Why option B is wrong?? can someone help.....

himanshu19

247 views

himanshu19 asked Dec 23, 2017

0 votes

0 answers

29

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

Hi mates, Show that it is ambiguous grammar TIAS->aAB/bBAA->bS/aB->aS/b

Sahil1994

239 views

Sahil1994 asked Nov 23, 2017

1 votes

1 answer

30

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 ... and (iii) are TRUE. Only (ii) and (iii) are TRUE. All of (i), (ii) and (iii) are TRUE.

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

Arjun

4.1k views

Arjun asked Nov 5, 2017

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