Linked Questions

(Practice exam question in computational models) Definition: A word $w\in \{0,1\}^*$ is called balanced if it contains the same number of $0$s as $1$s. Let $L = \{w\in \{0,1\}^*\mid |w|$ is even and ...

Is there an algorithm/systematic procedure to test whether a language is context-free? In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n a^n : n \in \...

$$\begin{align}L_1&= \{a^n b^m c^k\ |\ 0<2n\leq m\leq 3n, k = m, n, k,m\in \mathbb{N}\}\\ L_2&= \{a^n b^m c^k\ |\ 0<2n\leq m\leq 3n\text{ or }0<5n\leq m\leq 7m ,n, k, m\in\mathbb{N}\}\...

Let $ACFG$ be the language of all encodings $(C,x)$ where $C$ is a context free grammar that generates a language containing $x$, i.e. $ACFG$ is the acceptance problem for context free grammars. It ...

I tried to find a simple example for a language that is not parseable with an LL(1) parser. I finally found this language. $$L=\{\,a^nb^m\mid n,m\in\mathbb N,\>n\ge m\,\}$$ Is my hypothesis true ...

There are many techniques to prove that a language is not context-free, but how do I prove that a language is context-free? What techniques are there to prove this? Obviously, one way is to exhibit ...

For a language L we define: $\qquad A(L) = \{ x \in L \mid \text{ no proper prefix of x is in L} \} $ Are regular / context free languages closed under this operation ? For regular languages I ...

Is $a^mb^n$ where $m=n^2$ a CFL? I have a doubt regrading this problem. Say if we pop $n$ number of $a's$ from the stack for each $b$ then it is a CFL (to be exact DCFL) right? On the other hand I ...

I want to know if its possible to write a regular expression for a context free language: For example I have a language : L={a^n b ^m: n<= m +3} I have written the following regular expression ...

From Wikipedia: Off-side_rule#Implementation, there is a statement: ...This requires that the lexer hold state, namely the current indentation level, and thus can detect changes in indentation ...

We learned about the class of regular languages $\mathrm{REG}$. It is characterised by any one concept among regular expressions, finite automata and left-linear grammars, so it is easy to show that a ...

How I use the pumping lemma to prove that the language $L = \{ a^{j!} \mid j \geq1\}$ is not context-free?

When I prove some language is context free, It is too hard to find example string. Is there any tips? It takes too many time or eventually give up.

I'm trying to prove that that language isn't a context free: $ L = \{ w11w \mid w\in \Sigma^* = \{0,1\}\}$ I succeed to prove that $L = ww$ isn't context free, but not the language above. What ...

Could I get help to prove that the language $\{a^i b^j c^k \mid i>j>k\ge 0\}$ is not context free language by using pumping lemma?