Linked Questions

0 votes
0 answers
66 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 ...
user avatar
0 votes
0 answers
28 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 ...
user avatar
  • 319
0 votes
0 answers
63 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?
user avatar
  • 1
0 votes
0 answers
17 views

Language is regular via regular expression [duplicate]

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)^* \...
user avatar
  • 21
0 votes
0 answers
34 views

Avoiding pumping lemma [duplicate]

Is there a way to show $\{a^nb^nc^n:n\geq0\}$ is not regular without pumping lemma?
user avatar
0 votes
0 answers
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$?
user avatar
0 votes
0 answers
27 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 ...
user avatar
  • 121
0 votes
0 answers
38 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?
user avatar
0 votes
0 answers
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 ...
user avatar
  • 1
0 votes
0 answers
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 ...
user avatar
  • 1
0 votes
0 answers
81 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$...
user avatar
  • 307
0 votes
0 answers
35 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?...
user avatar
0 votes
0 answers
32 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 ...
user avatar
0 votes
0 answers
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. ...
user avatar
  • 1,719
0 votes
0 answers
55 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.
user avatar
  • 133

15 30 50 per page
1
2 3 4 5
11