CFG for L = { (+,-)* | #(-) - #(+) ≤ 3 at every position of the word }

73 Views Asked by At

I've tried to create my CFG, but I always ended with more doubts. For example, I'm suppose to accept the word "--+-++++" but not this one "+--++-----" I have tried the following grammar:

S-> -A | --A | ---A | A | ε

A-> +A | +S | + | -+ | +-

The main issue comes when the Grammar checks whenever there are enough "+" such that #(-) - #(+) is at most 3.

1

There are 1 best solutions below

0
On

Hint:

$$ \#(\texttt{-}) - \#(\texttt+) \leq 3 \Leftrightarrow \#(\texttt-) \leq 3 + \#(\texttt+) $$

Let's consider the following languages:

(a) $ \#(\texttt-) = 3 + \#(\texttt+) $

(b) $ \#(\texttt-) < 3 + \#(\texttt+) $

If we call $A$ the grammar generated by (a) and $ B $ the grammar generated by (b), then your grammar is: $$ S \to A \mid B $$

A little help:

$$ \begin{align*} A &\to K\texttt-K\texttt-K\texttt-K \\ K &\to K\texttt-K\texttt+K\mid K\texttt+K\texttt-K\mid\varepsilon \end{align*} $$

Try to think how you can construct the grammar $ B $ and you're done.