6 votes

Is there a one-state PDA that recognizes every context free language?

We have to be precise. Each context-free language can be accepted by empty stack using a push-down automaton with a single state, or by final state and two states. (In the latter case we obviously ...
Hendrik Jan's user avatar
  • 30.5k
5 votes
Accepted

Repeated rules with more than three symbols for conversion to Chomskys Normal Form

Yes, if the same strings are generated the productions can be shared. The "standard" conversion does not consider such "coincidences". Note that your final result does not yet ...
Hendrik Jan's user avatar
  • 30.5k
4 votes
Accepted

How it possible given string belong to given grammar

This is possible, provided there is a solution in nonnegative integers to the following pair of equations. $$ \left\{ \begin{array}{rcrc@{\qquad}l} x & + & 2y & = & 2020 \\ ...
Hendrik Jan's user avatar
  • 30.5k
3 votes
Accepted

Is there a linear language $L$ such that $\overline{L} \in \texttt{Type-2} \setminus \texttt{Lin}$?

It seems you almost solved the problem in your question statement. Note that the $n\neq m$ condition makes pumping hard: one needs a trick using factorials to succeed, see Prove if $L=\{0^m1^n∣m≠n\}$...
Hendrik Jan's user avatar
  • 30.5k
3 votes
Accepted

Accept $L=\{ww^r:w\in\Sigma^*\}$ in less that $|w|$ storage

It is (obviously) possible if $|\Sigma| = 1$ or $C = 1$. It is also possible for $|\Sigma| > 1$ and $C>1$. The idea is that you can use a bigger stack alphabet to encode multiple letters at once....
Nathaniel's user avatar
  • 13.9k
3 votes
Accepted

The complement of a particular language

The complement of the language $L = \{a^nb^n : n \in \mathbb{N}\}$ should actually be linear, if I'm not mistaken. Take some string $x \notin L$ over the alphabet $\Sigma = \{a, b\}$, since $L \...
Knogger's user avatar
  • 710
3 votes

Proving that L = {x ∈ {a, b}∗ | na(x) < nb(x) < 2na(x)} is not a context free language

The language is context-free. Slightly different: Context free grammar construction $\{ a^mb^n \mid m≤n≤2m \}$. For strings where the symbols $a,b$ may be in any order, you might find inspiration in ...
Hendrik Jan's user avatar
  • 30.5k
2 votes

Proving that L = {x ∈ {a, b}∗ | na(x) < nb(x) < 2na(x)} is not a context free language

Suppose that instead of a stack, you had a single counter, $x$, that you could either increment or decrement, under the control of a non-deterministic finite-state machine. (Each transition of the ...
D.W.'s user avatar
  • 158k
2 votes
Accepted

How to construct context-free language $L$ to prove $L′=\{x|xx∈L\}$ is not context-free?

Take a look at $$L = \{a^nb^nc^ma^mb^kc^l : n, m, k, l \geq 0\}.$$ Now take some $x \in L$ with $x = ww$, then $x = a^nb^nc^ma^mb^kc^l$ for some $n, m, k, l \geq 0$. There's only one possible way to ...
Knogger's user avatar
  • 710
2 votes
Accepted

Deciding if a language is CFL or in $P$

Observe that for some $c \in \mathbb{N}$ and finite alphabet $\Sigma$, $\Sigma^c$ with $|\Sigma^c| = |\Sigma|^c$ is finite. Therefore $$L_c = \bigcup_{u \in \Sigma^c} u\Sigma^*u$$ is the union of a ...
Knogger's user avatar
  • 710
2 votes
Accepted

Is $L=\{a^nb^m : n\neq 7m, \ n,m\in \mathbb{N}\}$ context free?

An easy way prove the language context free is to use the closure properties of context-free languages. Note that the following grammar with start variable $S$ generates $L' = \{a^nb^m : n = 7m\}$ $$S ...
Knogger's user avatar
  • 710
2 votes
Accepted

Context free grammar for $L=\{a^nb^m : 2m<n<4m\}$

The problem with your (new) solution is that you force $n$ to be equal to $3m$. That means that your grammar generates words that are in $L = \{a^nb^m\mid 2m < n < 4m\}$, but words in $L$ like $...
Nathaniel's user avatar
  • 13.9k
1 vote

Context free grammar for $L=\{a^nb^m : 2m<n<4m\}$

No. The grammar you propose is not correct. For example it generates $\varepsilon$, which is not in the language. In fact, no word generated by your grammar is in the language. To see this notice that ...
Steven's user avatar
  • 29.4k
1 vote

Proving that L = {x ∈ {a, b}∗ | na(x) < nb(x) < 2na(x)} is not a context free language

As the other answers indicate, the language is indeed context-free. Writing a grammar for it is a bit tricky, but we can do it as follows. $N_a(x) = N_b(x)$ First, let's consider the (much) simpler ...
ruakh's user avatar
  • 623
1 vote

How to construct context-free language $L$ to prove $L′=\{x|xx∈L\}$ is not context-free?

Context-free languages are not closed under intersection. We start there. The relevant example is here that $\{ a^p b^p c^q \mid p,q\ge 0 \} \cap \{ a^p b^q c^q \mid p,q\ge 0 \} = K$, where $K = \{ a^...
Hendrik Jan's user avatar
  • 30.5k
1 vote

Are there context-free languages whose both intersection and complement of intersection are non-context-free?

We can build a specific example over the alphabet $\{a,b,c\}$ as follows. Let $L_1 = \{ a^k b^m c^j \mid j < m \lor k < m \}$ and $L_2 = \{ a^k b^m c^j \mid k < 2m \}$. Obviously, $L_1 \cap ...
Mati's user avatar
  • 21
1 vote

Is $\{a^ib^ja^k \mid j \text{ is odd, then } k=i^2+j ;\ j \text{ is even, then } k =i+j\}$ context-free?

Note that the context-free languages are closed under left-quotient as well as intersection with regular languages, as John L. noted. Assume, for contradiction, that $L$ was context-free. Then $$L_1 :=...
Knogger's user avatar
  • 710
1 vote

Proving that the scramble of a regular language is context-free

We can prove this without using Parikh's theorem. Assume that a language $L$ over the two-letter alphabet $\{0,1\}$ is given by a finite-state machine. For the language $\mathrm{SCRAMBLE}(L)$ we ...
Mati's user avatar
  • 21

Only top scored, non community-wiki answers of a minimum length are eligible