Linked Questions

0
votes
1answer
57 views

The alphabet is {a, b}. Show that the set of words with the same number of occurrences of a and b is not regular [duplicate]

This is a question I've been asked to do and I honestly have no idea how to approach this. Help please?:)
0
votes
0answers
56 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 ...
2
votes
0answers
54 views

If there is comparison between two variables then language is not regular. Then how the below two languages L1 and L2 Regular? Please Explain [duplicate]

How these two languages be regular.If there is comparison between m and n since (n < m) is the condition to be satisfied.
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
51 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
2answers
40 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
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
0answers
37 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
37 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?
1
vote
1answer
26 views

Prove its not a regular language [duplicate]

I have a question. Assume $L = \{ a^m b^m \mid m ≥ 1 \}$ is not a regular language. Prove that $I = \{ a^{5n} b^{3m} c^n d^m \mid m,n ≥ 0 \}$ is not a regular language. I can prove it with pumping ...
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
29 views

Proving a language is Not Regular without using Pumping Lemma? [duplicate]

I was wondering how one would go about proving a language is Not Regular without using the traditional pumping lemma contradiction. $$L = \{ 1^k 0^n 1^n 0^k \mid k \geq 0, n \geq 0\}$$ I've seen a ...

15 30 50 per page