Regular languages are formal languages which are recognized by a finite automaton. It is equivalently the languages which are expressible as a regular expression. In addition to these two, there are several other equivalent definitions.
Questions tagged [regular-language]
1253 questions
2
votes
1 answer
Show that $L = \{a^p b^q \mid p, q \in \mathbb{N}^0 \setminus \mathbb{P}\}$ is not regular
Full disclosure: this is a homework question, so I'm only looking for a kick in the right direction.
The original question notes that $\{a^p \mid \ p \in \mathbb{P}\}$ is not regular and that the derivation should be possible using "the properties…
Nick Broderick
- 125
2
votes
2 answers
Creating a regular grammar
Hi I am trying to write a grammar for $L=\{xcy \mid x \neq y^R \land x,y \in \{a,b\}^*\}$.
I am not able to think beyond a point as to how to write the grammar. Could someone guide me?
Richa Sachdev
- 207
2
votes
0 answers
Is $L = \{a^n b^m b^m \mid n,m \ge 0 \}$ regular language or not regular language?
Is $L = \{a^n b^m b^m \mid n,m \ge 0 \}$ regular language or not regular language?
I think that $L$ is regular because the regular expression a*(bb)* describes this language. Is that correct?
mohamad rabee
- 151
2
votes
1 answer
Product of two DFA.
Let $ A, B \subset \{ a, b\}^* $ and $A, B$ be regular. Lets define: $ A \circ B = \{ w \in A | \exists y \in B , \#_aw = \#_ay \}$
where,for example: for $ w = aaabaaba$
$\#_aw = 6, \#_bw = 2 $
Prove, that $A \circ B $ is regular.
My idea:
Let…
user180834
- 1,453
2
votes
3 answers
Prove that language $L=\{a^ib^j:\gcd(i,j)=1\}$ is irregular
Prove that language $L=\{a^ib^j:\gcd(i,j)=1\}$ is irregular.
I have tried for a long time, but I haven't managed to solved it. Someone help me ?
user220688
- 509
2
votes
1 answer
Prove that this language is not regular
I need to prove that the language
$$L = \{a^nb^mc^k|n+k\neq3m\}$$
is not regular. Any ideas how I can do that?
2
votes
1 answer
Pumping lemma shows non-regular language, assignment suggests it is regular
In the assignment it asks us to show that
$$ L = \{0^kw0^k \mid k \ge 1 \text{ and } w \in \{0, 1\}^\ast\} $$
is regular (suggesting that it is in fact regular).
I don't believe that it is, so I tried using the pumping lemma to show this and it…
Evan
- 375
2
votes
1 answer
Equivalence classes in a regular language
Question:
Let L be a regular language, ~${_L}$ is it's equivalence relation (as was defined in Myhill Nerode theorem) that divides $\Sigma^* $ to 4 non empty equivalence classes A1, A2,A3,A4. Let $S=A1 \cup A2$. Prove that S is regular and that it's…
jreing
- 3,297
1
vote
1 answer
Prove regular languages closed under operation by changing alphabet?
Suppose we have the following language operation:
$Duplicate(L) = \{Duplicate(w)|w \in L\}$ where if $w=w_1w_2\ldots w_n$ $Duplicate(w) = w_1w_1w_2w_2 \ldots w_nw_n$.
It is simple to construct a DFA for this language, but is it valid to solve it by…
rkoth
- 33
1
vote
1 answer
Regular languages and intersection
Let L be a language and R an infinite regular one. If L intersection R is a regular language, then L is a regular one too?
gsamaras
- 413
1
vote
1 answer
DFA for {any sequence of a and b, between two consecutive "b" there are maximum 3 "a"}
I have tried to draw a deterministic finite automaton for the language L={any sequence of a and b, between two consecutive "b" there are maximum 3 "a"}:
Is it correct?
Mary Star
- 13,956
1
vote
3 answers
regular language question
Good afternoon everyone;
I am stuck with a question I could not find and answer by myself I hope you can help me.
My question is
The language L = {w : w {a,b}*, |w| is odd, w has exactly one b}.
Is this a regular language if yes could you draw…
Can
- 171
1
vote
1 answer
Pumping lemma $c^2a^nb^n$
I'm trying to prove that the following language is not regular via the Pumping Lemma. But I don't know, why is my procedure wrong (choosen word is incorrect according to my teacher).
$$L= c^+ \cdot \left\{w \in \{a,b\}^* \mid \text{count of a's in…
Milwoukee
- 31
1
vote
0 answers
Constructing a Turing decidable machine from DFA
I am a trying to prove that every regular language is decidable.
So in order to prove that I am trying to show that I can move from deterministic finite automaton (DFA) to a Turing decidable machine.
So I am not sure how to construct a Turing…
Ohad
- 111
1
vote
1 answer
Pumping Lemma - Clarification of Usage
I'd like to make sure my understanding of the Pumping Lemma is correct.
Consider $L=\{ 0^n1^m2^{n-m}:\, n \ge m \ge 0\}$
I'm going to give 2 solutions to prove that $L$ is not regular. One using "pumping down" and the other using a "cheap trick".…
EggHead
- 667