Linked Questions

0
votes
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.
0
votes
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 ...
0
votes
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.
2
votes
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 ...
0
votes
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 ...
0
votes
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?
0
votes
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 ...
1
vote
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?
0
votes
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?
0
votes
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 ...
0
votes
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. ...
0
votes
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$?
0
votes
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?
0
votes
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 ...
1
vote
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