# Tag Info

0

Several angles here. The distinction between "token" and "syntax" is somewhat arbitrary. Both can (and have been) described by CFGs. One reason for the split is that we read e.g. a C program in terms of tokens (variable names, operators, reserved words, comments), not in term of characters. So it makes sense for the compiler writer to do what comes ...

1

Let us define 4 non-terminals $X_{00}, X_{01}, X_{10}, X_{11}$ and the start variable $S$. The rules are as follow: \begin{align} S &\rightarrow X_{00},\\ X_{01}&\rightarrow \epsilon,\\ X_{00}&\rightarrow 0X_{10},\\ X_{00}&\rightarrow 1X_{10},\\ X_{01}&\rightarrow 0X_{11},\\ X_{01}&\rightarrow 1X_{00},\\ X_{10}&\rightarrow 0X_{00},...

2

The answer is no. Some context-free languages are inherently ambiguous: every context-free grammar defining a language of this kind will be ambiguous. An example is $$\{a^ib^jc^k \mid i = j \text{ or } j = k\}$$

0

Try to think of the CFG for $a^kb^k$, and for $b^mc^m$, and then make a grammar for the language $$L' = \{ a^kb^nc^m : m,n,k \in N^+ \wedge m+k=n\}.$$ After that, think of how you can change it to be a grammar for $L$.

0

I'm going to address the second part of the question first, about a "smarter grammar." One improvement that can be made is omitting the rules $$S \rightarrow Sc \hspace{10px}| \hspace{10px} Sd.$$ Assuming we have made that change, to answer the first part, if the grammar is correct we need to answer two questions. Does $S$ only generate strings within $L$?...

1

Since you didn't explicitly specify that $S'$ should be a context-free grammar, I'll take the opportunity to mention Boolean grammars, which are a fairly modest extension of CFGs that allow conjunction and negation in rules, in addition to the implicit disjunction of CFGs. The productions have the form A \to \alpha_1 \And \ldots \And \alpha_m \And \lnot\...

0

How about $\{a^{\Sigma(n)} \colon n \ge 1\}$, where $\Sigma$ is Radó's noncomputablr busy-beaver function?

6

Contrary to what you wrote, context-free languages are not closed under complement. See Examples of context-free languages with a non-context-free complements for some examples. As a result, there is no such algorithm. Also: It's decidable whether $L(S)=\emptyset$, but it's not decidable whether $L(S)=\Sigma^*$. If you could compute the complement, then ...

0

Regular expressions are recognized by finite state machines, while context free grammar recognized by push-down automata. Push-down automata is not efficient as FSM in terms of time, hence it's all about efficiency.

1

Have a good look to the answer you link to. It specifies the language that is generated using two numbers $k,\ell$. These numbers guarantee that the two parts are different without ever knowing where the middle of the string exctly was. I will try to explain. We have to find (or better, guess) a position in $x$ such that the same position in $y$ carries ...

1

There is a big difference between $\{ xy ∣ |x| = |y|, x = y \}$ and $\{ xy ∣ |x| = |y|, x \ne y \}$. In the first one, we need every symbol in $x$ to be the same as the corresponding symbol in $y$. For inequality, it suffices that at least one symbol in x be different from the corresponding symbol in $y$. The two cases are not symmetrical. Checking that ...

2

As a side note, that grammar is not written in BNF. Rather, it is written in one of many dialects of "extended" BNF, which includes repetition and optionality operators ({ … } and [ … ]). BNF only has simple productions. However, the repetition and optional components can be macro-expanded into BNF (using a newly-created non-terminal), and the "extended BNF" ...

1

The 'endless loop' is not a problem. Remember that there are many productions possible. A word is accepted by the grammar if there is any production that generates it. It doesn't matter if there are other productions (e.g., 'endless loops') that are pointless or never generate any word; they're harmless and irrelevant. No, this will not yield abababab.. ...

0

$\{a,b\}$ is set notation. The alphabet of a language is the set of all possible symbol used in the language. You can substitute the typical $\Sigma$ for the full set every time. $\Sigma^*$ (where $^*$ is the kleene star) is the set of all possible strings you can make with that alphabet. That includes strings that happen to not use a certain character. ...

2

Just show that after processing $0^n$ and $0^{n’}$ with n != n’ you must have reached two different states. (Which is easy: In one state, processing $1^n$ leads to an accepting state, in the other state it doesn’t). Therefore there is no finite set of states. Or you just take the pumping lemma, p arbitrary large, and w = $0^p 1^p$. Which makes y = $0^k$ ...

3

The languages of all palindromes is context-free. That does not implies that any language that contains only palindromes is context-free. For example, many language over the unary alphabet $\{a\}$ are not context-free. In fact, they can even be non-context-sensitive or undecidable. Note that any word over a unary alphabet is a palindrome. In particular, ...

Top 50 recent answers are included