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") ?
$\begingroup$
$\endgroup$
7
-
$\begingroup$ Are we speaking of context-free grammars? I would start from devising a CFG (possibly ambiguous) for that language... can you provide us one such grammar? $\endgroup$– chiOct 13, 2016 at 14:06
-
$\begingroup$ yes we have context-free grammar for that S->aSbS|bSaS|Ɛ but problem is that grammar is ambiguous $\endgroup$– mmsamieiOct 13, 2016 at 14:12
-
1$\begingroup$ You should be able to build a deterministic automaton that recognizes it. Then, using the algorithm described in a proof that deterministic implies unambiguous, you should be able to get the grammar you want. $\endgroup$– xavierm02Oct 13, 2016 at 14:45
-
1$\begingroup$ Linked: math.stackexchange.com/questions/388367/cfg-for-language/… $\endgroup$– xavierm02Oct 13, 2016 at 14:49
-
2$\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$– Raphael ♦Oct 13, 2016 at 14:57
|
Show 2 more comments
2 Answers
$\begingroup$
$\endgroup$
The problem with $S\to aSbS\mid bSaS\mid \varepsilon$ is that you're just making sure you match each $a$ with a $b$ (where we consider an $a$ and a $b$ to be matched iff they appeared during the same derivation step).
To ensure non-ambiguity, you must add a constraint on the matching to ensure that it is unique (while maintaining its existence). One way to do that is to make sure you match the first $a$ (resp. $b$) after your $b$ (resp. $a$) that hasn't been matched yet.
So you'd get something like $$ S\to aB S\mid bA S \mid \varepsilon\\ A \to a \mid b \square\\ B\to b \mid a\square$$
The idea is the following:
You want $S$ to generate words with as many $a$ as $b$s. At any points you can stop with the $S\to \varepsilon$. If you do add an $a$ with $S\to aBS$, then you need to add a $b$ later, and you put a $B$ to remind you of that, and then you continue with another $S$. The same things applies for $S\to bAS$.
If you have an $A$, it means that you are one $a$ short. If you read an $a$, everything is fine and you've got nothing else to do. But if you read a $b$, you are now two $a$s short. I left a $\square$ for you to fill to encode that.
$B$ works like $A$.
Solution :
You are two $a$s short so you are twice one $a$ short: $A \to a \mid b AA$. Similarly $B\to b\mid aBB$
For the proof, see this where $a,b,A,B$ are replaced with $0,1,O,I$ and your language is generated by $E$.
$\begingroup$
$\endgroup$
1
The ambiguity of the above grammar can be resolved as
S->aBS/bAS/ε
A->a/bAA
B->b/aBB
-
3$\begingroup$ What's the difference from the other answer? $\endgroup$– xskxzrApr 30, 2018 at 16:44