Linked Questions

1
vote
0answers
65 views

Proving a language is regular or non-regular [duplicate]

I'm struggling a bit to understand two of the problems we were given in class. Could someone look over my work and maybe give me a few hints? State whether the following languages are regular or not ...
1
vote
0answers
61 views

Show that a language is not regular using the Pumping Lemma [duplicate]

Possible Duplicate: How to prove that a language is not regular? Given a language $L = \{a^pb^{2p} \mid p \ge 1\}$, how could I show, using the Pumping Lemma that $L$ is not regular?
0
votes
0answers
61 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
56 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
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.
0
votes
2answers
49 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
41 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 ...
1
vote
1answer
31 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 ...
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
37 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
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?
-1
votes
1answer
34 views

Proving of regular language [duplicate]

Is this regular or not L = {w1w^R | w ∈ {0,1}* (where for any word w ∈ {0,1})*, w^R denotes the reverse of w)
0
votes
0answers
31 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
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 ...

15 30 50 per page
1 2 3
4
5
11