Questions tagged [ambiguity]

Questions about ambiguity in context-free grammars.

Filter by
Sorted by
Tagged with
4
votes
1answer
616 views

Is every unambiguous grammar regular?

While searching for an answer to this question I found out that there is an unambiguous grammar for every regular language. But is there a regular language for every unambiguous grammar? How can I ...
0
votes
3answers
132 views

Big O vs Big $\Theta$ during coding interview

Almost every time I see an article about time or space complexity, people are expressing the complexity with Big O, whereas it should be $\Theta$. From the book "Cracking the coding interview": "...
0
votes
0answers
27 views

Making context-free grammar unambiguous

I'm trying to change below context free grammar such that it becomes unambiguous, but I don't know what steps I should take. Is there any specific way of doing that? Here is my CFG: \begin{align} &...
2
votes
2answers
96 views

Unambiguous context-free grammar for strings with at least as many a's as b's

I have designed this Grammar but it is ambiguous: $$S\to aSbS \mid bSaS \mid aS \mid\epsilon$$ Would anyone help me make it unambiguous? Assume the alphabet is $\{a,b\}$.
1
vote
1answer
33 views

Is grammar that describes an equation in prefix (Polish) notation always unambiguous?

I recently completed a problem in which I was asked to generate a parse tree for the expression $+ \, 5 \, * \, 4 \, 3$ using the following grammar and rightmost derivation: $$Expr \rightarrow + \, ...
0
votes
0answers
26 views

Dangling Else Ambiguous Grammar

How is the following grammar ambiguous stmt -> if expr then stmt | matched_stmt matched_stmt -> if expr then matched_stmt else stmt | terminal
1
vote
0answers
95 views

Chomsky Normal Form for context free grammars ambiguous/unambiguous properties?

My textbook states: Finally, it must be stressed that the Chomsky normal form says nothing about ambiguity in general—a CFG in Chomsky normal form may or may not be ambiguous, just like we have for ...
0
votes
1answer
20 views

Ambiguous Grammar demostration exercise

Hi im stuck on an exercise of ambiguous grammar. I need an example that shows that this grammar is ambiguous. The grammar is defined as follows: $$S \rightarrow aT | bR$$ $$R \rightarrow a | aS | bRR$...
0
votes
1answer
310 views

Convert ambiguous grammar to unambiguous and SLR(1)

I have the following ambiguous operator grammar: E->E+E*E | E-E*E E->E+E | E-E | E+E | E*E | E/E E->(E) | x I must convert it to an unambiguous one ...
3
votes
0answers
174 views

Proper algorithm for resolving ambiguity in grammars via enforcing associativity and precedence rules

I was told there is a algorithm that always resolves ambiguity for grammars that have issues with precedence and associativity. I know ambiguity in general is undecidable, so I only want to resolve ...
6
votes
1answer
286 views

Are these special (one production) Context-Free Grammars always unambiguous?

Consider the following (Context-Free) Grammars with only one production rule (not including the epsilon production): $S \rightarrow aSb\;|\;\epsilon$ $S \rightarrow aSbS\;|\;\epsilon$ $S \rightarrow ...
1
vote
1answer
39 views

Is following grammar has language which is inherently ambiguous?

Grammar is as follow: $S \rightarrow aaAb | aab | A$ $A \rightarrow aaAb | aAb | \epsilon$ I think that this grammar has equivalent unambiguous grammar as follow. Let’s first rewrite the grammar ...
0
votes
1answer
260 views

Why ambiguous grammars are allowed for operator precedence parser?

I am aware of what is ambiguity, and why is it necessary to eliminate ambiguity in compilers in a certain context, but how can we allow ambiguity for operator precedence parser? Say I have a set of ...
30
votes
6answers
7k views

Why are ambiguous grammars bad?

I understand that if there exist 2 or more left or right derivation trees, then the grammar is ambiguous, but I am unable to understand why it is so bad that everyone wants to get rid of it.
0
votes
0answers
46 views

Is there any grammar parseable by LALR(1) but not LR(1)?

https://en.wikipedia.org/wiki/LALR_parser - as far as I understand, LALR(1) is a simplified version of LR(1), aiming to achieve a greater parsing performance at the expense of reduced power. So, IIUC, ...
0
votes
1answer
72 views

What are the sufficient conditions for a grammar to be unambiguous?

There is no algorithm that, given an arbitrary grammar, decides if it's ambiguous or not. However, Are there any sufficient conditions that make it easier to tell that a grammar is unambiguous? For ...
2
votes
1answer
224 views

Finding an unambiguous grammar of a language provided by a CFG

I'm working through 'Intro to Automata Theory, Language and Computation' 2nd edition by Hopcroft, Motwani & Ullman. In section 5.4, exercise 5.4.3 I am tasked with finding an unambiguous grammar ...
2
votes
1answer
36 views

Equivalent unambiguous grammar

Given the grammar: $S \to AS\mid \varepsilon$ $A \to A1\mid 0A1 \mid \varepsilon$ Generate a new unambiguous grammar that generates the same language as the grammar above. I have no idea how to ...
1
vote
1answer
142 views

Is there any relationship between grammar being ambiguous and the language itself?

According to my understanding, a grammar is ambiguous if it generate strings which can be interpreted in more than one ways ( that is , more than one parse tree), but when it comes to the language ...
2
votes
1answer
89 views

How to make an unambigous grammar of a programming language

We know that the decision problem of whether an arbitrary context-free grammar is ambiguous is undecidable. My question is how are made the unambigous grammar of programming language? My guessing is ...
0
votes
1answer
109 views

How to eliminate ambiguity of the follwing CFG?

Consider the following CFG: $S\to AED | F \\ A \to Aa | a\\ B \to Bb | b\\ C \to Cc | c\\ D \to Dd | d\\ E \to bEc | bc\\ F \to aFd | BC$ The CFG produces $a^*bbb...ccc...d^*$ (equal number of b,...
3
votes
1answer
72 views

unambiguous context-free languages and complementation

I was considering the following two natural questions about the relationship between unambiguity and complementation for the class of context-free languages: Is the complement of an unambiguous ...
1
vote
1answer
287 views

CFG - Ambiguous to Unambiguous

Given the ambiguous CFG : S → 01S1|SS|ϵ I came up with the following CFG which I think is unambiguous: S → 01X | 011X X → 01X1 | ϵ Is my CFG unambiguous and does it represent the same language?
2
votes
1answer
46 views

CFLs are inherently unambiguous?

As reading the textbook of Introduction to the theory of computation_third edition - Michael Sipser, which have the concept that we call a context-free language L inherently unambiguous if there does ...
2
votes
1answer
63 views

unambiguous equivalent grammar

There is a grammar G given: S->XaX X->aX|bX|eps I just replied to the first question that was ...
2
votes
0answers
57 views

Examples of context-free grammars whose ambiguity is unknown

Are there any examples of context-free grammars for which we simply do not know whether they are ambiguous? By examples I mean an actual specification for the grammar, not some kind of non-...
0
votes
1answer
322 views

Why postfix arithmetic expression is not ambiguous?

A binary tree can be written as an expression, no matter prefix, postfix or infix. But why an infix expression needs brackets, while the others don't? Say, why postfix, prefix produce only one binary ...
3
votes
2answers
603 views

How to check for ambiguous grammar if you don't know the string

Let's say I have a CFG grammar $G$ which describes some rules for language generation. How can you tell that grammar can generate ambiguous results for a string if you don't know that string? I know ...
4
votes
1answer
3k views

How to eliminate context-free grammar's ambiguity

I want to write a CFG that generates the words over {a,b} with the same number of ocurrences of a's and b's. I have come up with a couple of possibilties so far. I think they're correct but they're ...
1
vote
1answer
252 views

Are linear languages always unambiguous?

Deterministic Context free languages are always unambiguous. Now DCFL are a subset of linear languages. Are there any linear languages which are inherently ambiguous?
2
votes
1answer
692 views

Is this unambiguous grammar equivalent?

I have a simple context free grammar $(\{A\}, \{(,)\}, R, A)$, which consists of this one production rule: $A \rightarrow AA\, \vert\, (A)\, \vert\, \epsilon$ I believe this is ambiguous! For ...
0
votes
0answers
52 views

Is this grammar L4 ambiguous?

S-> AAB|ABA|BAA|epsilon A->aS B->bS this is a grammar of the language L4 = {w ∈ Σ*: #a(w) = 2#b(w)} over Σ = {a, b} Does the following examples shows that the L4 is ambiguous? S->AAB->aSAB->aAB-...
2
votes
1answer
2k views

Finding a unambiguous grammar

As an exercise we were supposed to find a grammar $G$ that generates language $L(G) = \{w \in \{a,b\}^* \mid |w|_a = |w|_b\}$. That was not so hard, I found a grammar which I think is correct: $S \...
1
vote
0answers
309 views

Given a context free grammar, prove if the grammar is ambiguous

Here is a context free grammar that I have been given for practice: Grammar $G = (V,\Sigma,R,S)$ where $V$ is $\{S,A,B,a,b,c\}$ and $\Sigma$ is $\{a,b,c\}$. $R$ has the following rules: $$\begin{...
3
votes
0answers
244 views

How would I build a parser generator for a context free grammar using Pushdown Automata?

I am building a parser generator, not for any project in particular, just for fun to improve my understanding of parsing, grammars, languages, etc. I am at the point where I have lexer generation ...
1
vote
1answer
67 views

Making a grammar ambiguous by applying a morphism

I have an encoding of an unambiguous grammar $G$. Can I apply a morphism $σ$ so that the grammar becomes ambiguous? I have no clear concepts about this, only the idea: "grammar $G$ is ambiguous if ...
1
vote
0answers
166 views

Context Free Grammar Prove Un-/Ambiguity

I know, it is not possible to decide whether a context free grammar is ambiguous or not. However, I am having a really hard time preparing for an upcoming exam in which I'll have to give a prove of un-...
4
votes
1answer
571 views

How to find unambiguous grammar for palindromes

I am trying to figure out how to make an unambiguous grammar for palindromes over the alphabet {a, b}. I have the following, but it is ambiguous and causes conflicts in yacc. ...
9
votes
2answers
981 views

Is there a different resolution of the “dangling else” problem other than “match closest”?

The following context-free grammar presents a "dangling else" type ambiguity (imagine that $a$ stands for if expr then and $b$ stands for ...
2
votes
4answers
595 views

How to prove that Ambiguity is still present in Resolved Production of Dangling Else Problem?

$\textbf{stmt} \to$ $ \textbf{if} $expr$ \textbf{then}$ stmt $\mid $ $\textbf{if}$ expr $ \textbf{then}$ stmt$ \textbf{else}$ stmt $\mid \textbf{...
5
votes
2answers
4k views

unambiguous grammar that produce equal number of a and b

is there any unambiguous grammar on alphabet={a,b} that can produce strings which have equal number of a and b (e.g. "aabb" , "baba" , "abba") ?
0
votes
1answer
6k views

How to find whether a grammar is ambiguous?

$$S\rightarrow aAB$$ $$A\rightarrow bBb$$ $$B\rightarrow A|\epsilon$$ I'm choosing the string abbbb. First left most derivation is the following: $$S\Rightarrow aAB\Rightarrow abBbB\Rightarrow ...
0
votes
0answers
985 views

Show that any LL(k) grammar is unambiguous

I am confused on several areas of this. First, this is so obvious I am finding it hard to prove. Second, what are some definitions, axioms, or lemmas of an ll(k) grammar that I can use to build up a ...
-1
votes
2answers
425 views

Find the Unambiguous Grammar [closed]

Consider the following grammar: S->A. A->A+A|B++. B->y Check whether grammar is Ambiguous or not? Also ,unambiguate the grammar.Now please tell me what will be the grammar after removing the ...
0
votes
1answer
585 views

It has been asked to prove that a grammar is unambiguous which seem ambiguous to me

S->aAB A->bBb B->A|epsilon It seems that the string abbbb can be derived by using more than one ways. After using the starting production and the ...
2
votes
1answer
712 views

Find unambiguous grammar for an ambiguous grammar

Hi I want to find an unambiguous grammar for a known ambiguous one, and the production is like this: S->bA|aB A->a|aS|bAA B->b|bS|aBB I have found the ...
3
votes
0answers
247 views

How to refactor a grammar to be suitable for recursive descent?

I'm trying to learn how to use a recursive descent parser, and reading on this page I find this example: $S \rightarrow AB \\ A \rightarrow a \\ A \rightarrow SA \\ B \rightarrow b \\ B \rightarrow ...
2
votes
1answer
90 views

Explanation of Grammar Ambiguity

Consider now the grammar G S -> (S + S) S -> (S * S) S -> a Is it ambiguous? Answer: No because there are disambiguating parentheses and so no left or right recursion. Can someone explain how the ...
6
votes
4answers
4k views

Big Oh vs Big Theta

I mathematically understand $f(n) \in O(g(n))$ : $f(n)$ does not grow faster than $g(n)$. More formally, $\exists c, n_0$ s.t. $f(n) \leq cg(n) \forall n \geq n_0$. Similarly, $f(n) \in \Theta(g(n))$...
1
vote
1answer
74 views

Ambiguity Problem (Language Structures)

I'm having serious issues fining an unambiguous version of a particular grammar. I've looked online for help for this particular problem and for general methods for finding unambiguous versions of ...