New answers tagged

0

As @nir_shahar said the mentioned language is equivalent to $L((a \cup b)^*)$, hence the grammar may be written much simpler: $$ S \rightarrow aS | bS| \epsilon $$


2

This CFG is indeed correct, but can be greatly simplified. First, there is no need to create a new variable that would derive only a terminal value, that is - $s_1,s_2,s_5,s_6$ are not required. For a similar reason, we don't need $s_9$. Another simplification is that $(a\cup b)^*$ was already generated by $s_4$. There is no need to create $s_7$ and $s_8$ ...


2

Suppose that $C$ were context-free. Then the following language would also be context-free: $$ C' = C \cap 0(100+110)^+0. $$ What does $C'$ look like? Suppose that $x = wzzw^R$ belongs to $0(100+110)^+0$, where $z,w \neq \epsilon$. Note that the first two symbols of $x$ are $01$, and last two are $00$. This shows that $w = 0$, and so $zz$ belongs to $(100+...


2

You can use the pumping lemma to prove that the language is not context-free. Suppose $B$ is context-free and let $n$ be the constant of the pumping lemma. Consider the word $u = 0^n1^n2^{n^2+1} \in B$. Then we can write $u = vwxyz$ such that: $|wxy| \leq n$; $|wy| > 0$; $\forall k\in \mathbb{N}, vw^kxy^kz \in B$ Now since $|wxy| \leq n$, we either have ...


1

The answer in that image is actually not a deterministic PDA, because in the definition of DPDA, the transition functions need to satisfy the following rules: 1. $\delta(q, a, b)$ contains at most one element; 2. if $\delta(q,\lambda,b)$ is not empty, then $\delta(q,c,b)$ must be empty for every $c\in\Sigma$. These two rules prevent multiple paths for same ...


1

In a related question you obtained a context-free grammar for this language. $S\to bSa \mid A\mid B$ $A\to aA \mid a$ $B\to bB \mid b$ Although I agree with Yuval that directly constructing a push-down automaton shows you understood the concepts of a PDA, I like to recall that there are direct constructions between PDA and CFG. As wikipedia mentions the ...


1

The PDA has two main states: No $a$ has been encountered. Some $a$ has been encountered. While in the first state, it pushes $B$ onto the stack for any $b$ it encounters. It moves to the second state when encountering an $a$, at which point it removes $B$ from the stack for any $a$ it encounters (including the first $a$). If it ever realizes that it has ...


5

Clearly we cannot keep both the number of $a$'s and the number of $b$'s on the stack, because what order should we use. The solution (I think) is to keep the difference of these numbers on the stack. Or better, the difference between the promised numbers in the DFA computation on word $x\in L$ that we guess, and those that are realised by the (permuted) word ...


5

For every symbol $\sigma_i$ that the PDA reads, it guesses a symbol $\tau_i$. It simulates the DFA on the word $\tau_1 \ldots \tau_i$, and will only accept if the DFA accepts. Using the stack, it maintains the following counter: $$ (\#_a(\sigma_1 \ldots \sigma_i) - \#_b(\sigma_1 \ldots \sigma_i)) - (\#_a(\tau_1 \ldots \tau_i) - \#_b(\tau_1 \ldots \tau_i)), $...


4

A word in $L$ must either be of the form $b^i a^j$ with $i \neq j$ or it must have $ab$ as a substring. Therefore you can write a context-free grammar $G$ for $L$ as the union of two context-free grammars $G_1$ and $G_2$ for $L_1 = \{b^i a^j \mid i \neq j\}$ and $L_2 = \{w \in \{a,b\}^* \mid ab \mbox{ is a substring of } w\}$. It is easy to come up with a ...


1

How about \begin{align*} S&\to q\mid w\mid qqB \mid wwB \mid qwA\mid wqA\mid \varepsilon \\ A&\to qB\mid wB \\ B&\to qB\mid wB\mid \varepsilon \end{align*} We can just explicitly include strings of length 0, 1 or 2 that are allowed, but add another non-terminal after the length two strings which are not allowed to force us to add at least one ...


4

It looks like by describing your "CFG+" grammar, you have independently reinvented/rediscovered the conjunctive grammar. Here is more quote from that article on Wikipedia. The family of conjunctive languages is closed under union, intersection, concatenation and Kleene star, but not under string homomorphism, prefix, suffix, and substring. Closure ...


0

Every such grammar will describe a context-sensitive language: every context-free language is also context-sensitive, and context-sensitive languages are closed under intersection. I don't know if this describes a proper subset of the context-sensitive languages, or if every context-sensitive language can be formulated in this way.


2

Let us see which words satisfy $C_2(w) = w^R$. Write $w = \sigma \tau x$, where $\sigma,\tau \in \Sigma$ and $x \in \Sigma^*$. Then $C_2(w) = x \sigma \tau$ and $w^R = x^R \tau \sigma$, and so $C_2(w) = w^R$ iff $x = x^R$ and $\sigma = \tau$. You should be able to use this information in order to construct a grammar for your language.


1

Let $n = n'+1$, $m = m'+1$. Then $m < n/2$ translates to $n'+ 1 > 2(m+1)$, i.e. $n' \geq 2m'+2$. Therefore we can write the language as $$ \{ a^{1+2m'+2+k}(bc)^{1+m'} : m',k \geq 0 \} = \{ a^3 a^k (a^2)^{m'} (bc)^{m'} bc : m',k \geq 0 \}. $$ You take it from here.


1

Denote your language by $L$. Notice that $$ L \cap 1^*\#0^*1 = \{ 1^n \# 0^n 1 : n \geq 0 \}, $$ which should suffice for showing that $L$ isn't regular. On the other hand, $$ L = \{ 0^a1^n \# 0^n 10^b : n,a,b \geq 0 \} \cup \{ 0^ax01^n \# 0^n1x^R0^b : n,a,b \geq 0, x \in \{0,1\}^* \}, $$ which should suffice for showing that $L$ is context-free.


0

This grammar is ambiguous grammar, so it is not in LL(1):


2

One direction is easy. To prove that $L(G) \subseteq L$, we prove by induction on the length of the derivation that every word generated by $G$ has an equal number of 0s and 1s. This amounts to proving the following statements: $\epsilon \in L$. If $x,y \in L$ then $xy \in L$. If $x \in L$ then $0x1,1x0 \in L$. The other direction, proving that $L \...


4

In order for their example to work, the authors need identifiers to be of unlimited length. This is because the language $$ \{ wcw : w \in \{a,b\}^*, |w| \leq n \} $$ is context-free (indeed, regular). The syntax of a language like Pascal or Algol is context-free. This accomplished by waiving the requirement that an identifier be declared before its usage; ...


2

Defining the grammar in terms of an abstract $id$ token allows you to write a context-free grammar for a language which would otherwise be context-sensitive, by dropping restrictions from the grammar. Something like FUNCDEF ::= 'func' ID '(' PARAMDEF ')' FUNCBODY and FUNCCALL ::= ID '(' ARGS ')' This is perfectly context-free, by simply treating the $id$ ...


5

Your grammar doesn't seem to generate $caac$. Indeed, in order to generate this work, a simple case analysis shows that the derivation must start $$ S \to cYc \to caYYc, $$ at which point it is clear that we cannot generate $caac$. I assume you know how to generate the language $c\Sigma^*c$, as well as the language of all words with an equal number of $a$-s ...


Top 50 recent answers are included