New answers tagged

2

In fact, every non-trivial language is $\text{R}$-hard. That is, every decidable language is reducible to every non-trivial language. Indeed, let $A$ be a decidable language, and let $B$ be a non-trivial language. A reduction from $A$ to $B$ operates as follows. On input $x$, check whether $x\in A$ (this can be done as $A$ is decidable), then: if $x \in A$, ...


1

As shown here, minimizing the states in an LR(1) parser is NP-hard. The basic idea is that given an arbitrary graph, you can construct a grammar such that for every node in the original graph, the LR(1) parser contains a corresponding state in its state graph, and two states can be merged if and only if there is no edge between them in the original graph. ...


2

Let $L$ be a regular language, then $L$ has both a left linear grammar and a right linear grammar. The right linear grammar $G_R$ has axiom $S_L$ and productions of the form $A\to_R aB$ or $A\to_R\varepsilon$, and the left linear grammar has axiom $S_L$ and productions of the form $P\to_L Qa$ or $P\to_L\varepsilon$. Note that the left linear grammar is ...


0

Here is a sketch of an NPDA for $L^{|2|}$ given a regular language $L$. If $L$ is regular then it has a DFA $M$. We assume for simplicity that $M$ has one final state only. Create two NPDA from $M$. One is $M_{push}$ which is $M$ but with a stack such that every time it reads an input it pushes a symbol, say $X$. The other NPDA is $M_{pop}$ that pops the ...


2

Let $\mathcal{A}$ be a DFA for $L$. A direction is to consider a PDA $\mathcal{B}$ for $L^{|2|}$ that is defined on top of the product of $\mathcal{A}$ with itself, that is, the state-space of $\mathcal{B}$ is $(Q_{\mathcal{A}} \cup \{ null\})\times Q_\mathcal{A}$, where $null$ is a special state that is not in $Q_{\mathcal{A}}$, to be explained below. The ...


4

Let $\Sigma' = \{\sigma' : \sigma \in \Sigma\}$ be a tagged version of the alphabet of $\Sigma$. Let $L'$ be a version of $L$ obtained by tagging all letters. Let $h\colon \Sigma \cup \Sigma' \to \Sigma$ be a homomorphism which removes tags. Then $$ L^{|2|} = h(LL' \cap \{xy : x \in \Sigma^n, y \in \Sigma^{\prime n} \text{ for some } n\}). $$ Standard ...


1

Let $F$ be the set of finite languages $R$ be the set of regular languages $C$ be the set of context-free languages. The statement "All finite languages are regular" can be rewritten $F \subseteq R$. Similarly, "All regular languages are context-free" can be rewritten $R \subseteq C$. Both being true, we can take $F \subseteq R \land R \...


16

The language consisting of the words $w_1,w_2,\ldots,w_n$ is generated by the context-free grammar $$ S \to w_1 \mid w_2 \mid \cdots \mid w_n. $$


2

Let's write the condition $x+w=y+z$ in a different way: $x-y=z-w$. We consider two cases: $x \geq y$ and $y \geq x$. If $x \geq y$, let $x = y+a$. Then we are interested in words of the form $$ 0^{y+a} 1^y 0^{w+a} 1^w = 0^a 0^y 1^y 0^a 0^w 1^w. $$ If $y \geq x$, let $y=x+b$. Then we are interested in words of the form $$ 0^x 1^{x+b} 0^z 1^{z+b} = 0^x 1^x 1^b ...


1

I don't know if $x$, $y$, etc. can be $0$, so maybe there's something to fix (e.g., you'll need $S\rightarrow \varepsilon$ etc.), but you can try something like this: $S\rightarrow 0S1 \mid 0A0 \mid 1B1 $ $A \rightarrow 0A0 \mid 1C0$ $B \rightarrow 1B1 \mid 1C0$ $C \rightarrow 1C0 \mid \varepsilon$ Suppose $w\geq x$, then the idea is first generating the ...


0

Your language consists of all strings with an even number of $a$'s and an odd number of $b$'s. How do we construct a regular expression for such a language? Let us assume for starters that the word starts with $bb$. Thus, it has the form $$ bba^{n_1}ba^{n_2} \ldots ba^{n_m}, $$ where $m$ is even and $n_1+\cdots+n_m$ is even. This suggests grouping the $b$'s ...


1

Note that your grammar is regular. Quoting from wikipedia: A grammar is regular when no rule has more than one nonterminal in its right-hand side, and each of these nonterminals is at the same end of the right-hand side. Every regular grammar corresponds directly to a nondeterministic finite automaton, so we know that this is a regular language. In theory, ...


0

It seems to me that you may simply consider the automata with states S, A, B, C and exit state X, and with the following transitions: S -a-> A S -b-> C S -b-> X A -a-> S A -b-> B B -a-> C B -b-> A B -a-> X C -a-> B C -b-> S Right?


4

This question shows the pitfalls of applying algorithms without understanding how they work. There is absolutely no problem with applying an algorithm mechanically, but in that case, you should make sure that the algorithm you are applying is 100% correct, and that you are following it 100% accurately. How does the $\epsilon$-removal work? Suppose that we ...


2

You already lost the $010$ word when you've removed the $A\to \epsilon$ rule. In $G'$, which is the grammar you got by removing $\epsilon$-rules, you also need to add the $A \to 01$ rule.


2

If the context-free grammar is unambiguous, you can count the number of sentences it generates in a linear scan with a carefully chosen order. I'll assume we have removed all useless symbols and cycles from the grammar. If it is finite and free of useless symbols and cycles, then it should not contain any recursion. Let $N(A)$ denote the number of sentences ...


2

I am afraid that there is no better general result than the obvious one. Assume that $\mathcal K$ and $\mathcal L$ are two families of languages with $\mathcal K\subset \mathcal L$ such that $\mathcal L$ is closed under the operation $\circ$. Then for $K\in\mathcal K$ and $L\in \mathcal L$ we have $K\circ L\in \mathcal L$. This is obvious, as both $K,L\in \...


2

If $L_0$ in a context-free language, this doesn't guarantee that its complement is context free. For example, consider the language $$L_0 = \{a,b,c\}^* \setminus \{a^nb^nc^n : n \geq 0\}.$$ This language is context-free, but is complement (with respect to $\{a,b,c\}$) is not. Another way to formulate your question is as follows: given a context-free grammar ...


1

The first step is finding a simpler description of the language generated by the grammar $S \to aSbS \mid \epsilon$. The second step is deducing a description of the complement, which is the language you're actually interested in. Finally, in order to show that the language is context-free, you can consult our reference question on this topic.


0

When it comes up to deciding if a language is context-free or not, I try the following 'roadmap' to come up with an answer. $1.$ Try to make a CFG for the given language. If we can make a CFG, we have proved that the language is context-free. $2.$ If step $1$ did not work out, there is a probabilty that the language is not context-free. So try proving that ...


2

Here are a couple of pertinent references which support the idea "It mostly doesn't matter/write your own": different parsing approaches: https://code.jsoftware.com/wiki/Guides/Parsing a simple table-based (state machine) parser: https://www.jsoftware.com/help/dictionary/dicte.htm


3

The set of all regular languages is a subset of context free languages. So if you have a context free grammar (CFG) that generates a regular languages, you most certainly can convert it to a regular expression (RE), regular grammar (RG), or finite automata (FA). Before I go further with your example, I will simplify it so that we only deal with 3 terminals (...


3

If a word is not of the form $w\#w$ then one of the following must happen: It contains no $\#$. It contains more than one $\#$. It is of the form $x\#y$, where $x,y \in \{0,1\}^*$ and $x \neq y$, in which case one of the following must happen: $|x| > |y|$ or $|x| < |y|$. $x_i = 0$ and $y_i = 1$ for some $i$, or vice versa. The only case which is non-...


Top 50 recent answers are included