Linked Questions

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
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$ ...
0
votes
0answers
24 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 ...
0
votes
0answers
21 views

Pumping lemma with two r languages [duplicate]

I have two questions about how to use pumping lemma for regular languages to show that two languages are not regular. I would appreciate if someone can confirm if my answers make sense, and if not, ...
0
votes
0answers
19 views

Regular grammar question [duplicate]

Define a regular expression such that there is a string of 1 or more a's continuous followed by a continuous string of b's so that the number of a's and b's are the same. I have ideas on how i would ...
0
votes
0answers
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)^* \...
0
votes
0answers
16 views

Proof that $L = \{w | na(w) + nb(w) = nc(w)}\ is not regular [duplicate]

So.. my professor mentioned that it has something to do with $Wi = a^5b^i$ $Zij = c^(i+5)$ which is in the language But then mentioned that $Wj = a^5b^j$ $Zij = c^(i+5)$ Is not in the language, ...
0
votes
0answers
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 ...
0
votes
0answers
13 views

Prove if {a^i b^j | i ≤ j} is a regular language or not [duplicate]

How can i prove if this language is regular or not? (i think is non regular)
91
votes
5answers
70k views

How to prove that a language is not context-free?

We learned about the class of context-free languages $\mathrm{CFL}$. It is characterised by both context-free grammars and pushdown automata so it is easy to show that a given language is context-free....
50
votes
8answers
81k views

How to prove a language is regular?

There are many methods to prove that a language is not regular, but what do I need to do to prove that some language is regular? For instance, if I am given that $L$ is regular, how can I prove that ...
20
votes
4answers
64k views

How to show that a “reversed” regular language is regular

I'm stuck on the following question: "Regular languages are precisely those accepted by finite automata. Given this fact, show that if the language $L$ is accepted by some finite automaton, then $L^{...
19
votes
4answers
7k views

Using Pumping Lemma to prove language $L = \{(01)^m 2^m \mid m \ge0\}$ is not regular

I'm trying to use pumping lemma to prove that $L = \{(01)^m 2^m \mid m \ge0\}$ is not regular. This is what I have so far: Assume $L$ is regular and let $p$ be the pumping length, so $w = (01)^p 2^p$....
9
votes
3answers
2k views

How to feel intuitively that a language is regular

Given a language $ L= \{a^n b^n c^n\}$, how can I say directly, without looking at production rules, that this language is not regular? I could use pumping lemma but some guys are saying just looking ...

15 30 50 per page
1
3 4
5
6 7
11