# Linked Questions

149 questions linked to/from How to prove that a language is not regular?
0answers
53 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.
0answers
52 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 ...
0answers
50 views

### Proving that $\{0^nw1^n\mid n\geq 0, w\in\{0,1\}\}$ is irregular [duplicate]

How can I prove that the language $L = \{0^nw1^n\mid n\geq0,w\in\{0,1\}\}$ is irregular? I've tried the pumping lemma but that seems not to work.
0answers
40 views

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 39 views ###$L = \{a^{n^3} | \ge 0\}$Use the Pumping Lemma to show that L is not regular [duplicate] Use the Pumping Lemma to show that$L$is not regular: $$L = \{{a^{n^3} | \ge 0}\}$$ I feel like I have a good intuition of what the Pumping Lemma states; strings that belong to a regular language ... 2answers 39 views ### Is there a regular grammar for the language$\{ w : |w|_0 = |w|_1 \}$? [duplicate] I need to prove whether the language$ L = \{w \in \{0,1\}^* \mid |w|_0 = |w|_1 \}$can be written as a regular grammar. Obviously it can, but how do I prove it? 0answers 36 views ### Proof that {w ∈ {a, b} ∗ | |w|a = |w|b} is not a regular language [duplicate] I know that the language {w ∈ {a, b}∗| |w|a = |w|b} is not regular since somehow, you can't store all the information needed in a DFA. I've seen that normally it's done with reduction to absurdity or ... 0answers 35 views ### what is complexity of language {a | a = x^2 } [duplicate] What is known complexity of language {a | a = x^2}, is it possible there exist deterministic Turing machine (one input tape and one work tape) that accept this language in linear time? 0answers 34 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 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 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 26 views ### Avoiding pumping lemma [duplicate] Is there a way to show$\{a^nb^nc^n:n\geq0\}$is not regular without pumping lemma? 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 25 views ### How to show that a languge is not regular [duplicate] How can I show that this language is not regular? $$L = \{a^n (ca)^m b^{n+1} \mid m \ge 0 , n \ge 0 \}$$ This is my attempted solution: Assuming the pumping number to be$p$and making$m=0\$ ...

15 30 50 per page