Linked Questions

0answers
83 views

Proof that the language is not regular (Pumping Lemma) [closed]

I have to prove that the following language is not regular: $$\{ x | x = 10^{2n} + 10^n + 1, n ≥ 1\}$$ I am trying to prove it using Pumping Lemma, however, when I expand the expression I have both ...
1answer
68 views

Using closure properties to show that $L_1=\{a^lb^mc^m|l,m\ge 0\} \cup L(b^*c^*)$ is regular or not

i'm trying to figure out whether this Union $\left [ L_1=\{a^lb^mc^m|l,m\ge 0\} \cup L(b^*c^*)\right]=K$ is regular or not, now since regular languages are closed under intersection, so i assume $K$ ...
1answer
68 views

How construct PDA to $L = \{x \in(a,b,c,d)^* \mid -10 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 10 \}$

$L = \{x \in(a,b,c,d)^* \mid -10 \leq ( |x|_a + |x|_b) - ( |x|_c + |x|_d) \leq 10 \}$ I don't have any idea. Can someone help me.
1answer
66 views

Acceptance problem for CFGs is not regular

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 ...
1answer
40 views

Is the language in the description context free? [closed]

I am stuck on a question. Lets say there is a string that can be created from three alphabets a,b,c the condition is number of a<= number of b<= number of c. I can solve if there are a and b (...
1answer
34 views

How to prove that a language is not context-free using pumping lemma

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 ...
0answers
41 views

Language involving length constraints and reversal

Why is the language $A=\{wtw^r: w,t\in\{0,1\}^*\text{ and }|w|=|t|\}$ not a context free language? It is turning out to be really tricky. Is there an easy way to show this?
0answers
40 views

How to use homomorphisms to prove irregularity [duplicate]

I'm a bit confused on how to use homomorphims to prove irregularity or to prove that a language is not context free. This is what I'm currently thinking: Example 1: Let \$L = \{ a^{i}b^{j}c^{k} : i ...
0answers
22 views

Need some guidance on CFG pumping lemma proof

I'm currently stuck on a homework problem, and I feel completely lost about how to solve it. Generally I find pumping lemma proofs to be pretty straight-forward, but I feel like I'm missing something ...

15 30 50 per page