157 questions linked to/from How to prove that a language is not regular?
59 views

### Can't tell whether the following language is regular or not: [duplicate]

I have to decide if the following language is regular or not. I suspect it is not regular, so I try using pumping lemma to prove it, but something goes wrong. Any help on how to use pumping lemma on ...
25 views

### Pumping lemma for non regular languages [duplicate]

I read that pumping lemma is sufficient condition to prove non regularity of languages but not necessary condition. I know the first part that it is sufficient is true but not able to understand why ...
60 views

### proving L = {$a^{100}yy^r : \forall y \in$ {a,b}*} is not regular

I need to prove that L = {$a^{100}yy^r : \forall y \in$ {a,b}*} is not regular. i have tried using pumping lemma but couldn't get far with it. Any help in where i should go with it?
17 views

I was wondering if this language is regular L={$a^{2m+k}b^{3n+l}c^{m+n}$ & $k>2$ & $l \le 3$ & $m,n \in \mathbb{N}$} .I think the regular expression is : $(aa)^*aaa(a)^*(bbb)^* \... 0answers 29 views ### Avoiding pumping lemma [duplicate] Is there a way to show$\{a^nb^nc^n:n\geq0\}$is not regular without pumping lemma? 0answers 28 views ### How to make finite automaton for this language? [duplicate] Consider the language $$L = \{0^p 1^q 0^p | p, q ≥ 0\}.$$ How to make a finite automaton for$L$? How to make a regular expression for$L$? 0answers 24 views ### How to apply the pumping lemma to this CF string? [duplicate] I am struggling understanding how to apply to pumping lemma to a CF string. I've got this string: $$a^{n}b^{n}c^{m}$$ I would like to understand the steps to apply the pumpuing lemma for this ... 0answers 35 views ### Proofing with Pumping Lemma [duplicate] Considering a DFA that has an alphabet of {A,B}, and where number of characters A > number of characters B. I don't think such a DFA is possible. Can I proof the impossibility with a Pumping Lemma? 0answers 15 views ### Struggling with Pumping Lemma application [duplicate] I have studied Pumping Lemma carefully and have solved many exercises about it but I can't get an idea on how to solve this one: can anyone help me? Let L = { w#x | x is a substring of w }. Prove ... 0answers 25 views ### Proof by pumping lemma [duplicate] I'm trying to use the pumping lemma proof to show that the following language is context-free rather than regular$\{ba^n bc^n | n \geq 1\}$I've been looking at tutorials on Youtube to try and ... 0answers 62 views ### How to prove that the language of words ucv with as many a's in u as b's in v is irregular? I'm trying to prove that:$L=\{w\in\{a,b,c\}^*\Big|\#_a(u)=\#_b(v),\ \ w=ucv,\ \ \ u,v\in\{a,b\}^*\}$is irregular, so I'm trying to use the Pumping Lemma. This is what I tried so far:$w=a^ncb^n$... 0answers 31 views ### Language of strings of lengths that are prime is regular? Is C^* regular? [duplicate] With$\Sigma = \{a\}$I want to see if a language$C = \{a^p \ | \ p \ \text{is prime}\}$is regular and whether or not$C^*$is regular. How would I go about showing whether$C$or$C^*$are regular?... 0answers 31 views ### Can somebody please explain what the pumping lemma is? [duplicate] I've had multiple lectures on the pumping lemma but still can't grasp exactly what it is...my main questions are as follows What is the pumping lemma for? How do you use it to prove a language is not ... 0answers 31 views ### For the langauge L={0^i1^i | i>=0} DFA possible or not? [duplicate] At many places I have read that the following language is not a regular, and thus it is impossible to express this in terms of Finite Automata. L={0^i1^i | i>=0} But I tried this as follows. ... 0answers 54 views ### Show that a language is not regular by Pumping Lemma [duplicate] Possible Duplicate: How to prove that a language is not regular? Show that$L_2=\{a^nb^k|n\not= k-1\}\$ is not regular by Pumping Lemma.

15 30 50 per page