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
0
votes
3 answers
Proving a language is regular
I know to prove a language is regular, drawing NFA/DFA that satisfies it is a decent way. But what to do in cases like
$$
L=\{ww \mid w \text{ belongs to } \{a,b\}*\}
$$
where we need to find it it is regular or not. Pumping lemma can be used for…
Richa Sachdev
- 207
0
votes
2 answers
Regularity of a language
$$
L = \{w \mid w \text{ does not contain } 000\}
$$
$$
L_2 = \{w \mid xwy \in L \text{ for some } x,y \in (0+1)^*\}
$$
Is $L_2$ regular? I am thinking regular language is closed under concatenation, but it seems that this language should be…
Louis Kuang
- 293
0
votes
1 answer
Proof of L being a regular languaje
I have the following language
$$L = \{w\in\{a,\;b\}^* : a^nv,\; n\geq 1 \wedge |v|_a \geq n\}$$
Formed by characters "$a$" and "$b$" where the word $v$ has more "$a$" characters than $a^n$.
I have to prove that this is a regular language, but I…
Manuel W.
- 33
0
votes
0 answers
Proving by using intersection construction that language is regular
L is a regular language and Σ is the alphabet . Proof using intersection construction that L' is a regular language.
two muppets http://imageshack.com/a/img661/4318/T38eP9.png
which languages I should intersect?
mohamad rabee
- 151
0
votes
1 answer
Check if language and complement is context free
$L=\{u\$w^R|u,w\in \{a,b\}^+ \text{$w$ is prefix and suffix of $u$ }\}$
Check if language $L$ and $L^C$ is context free.
L
$a^*b^*\$a^*b^*\cap L = \{a^ib^j\$a^ib^j|i, j\ge 0\}\notin CFG$
So, $L$ is not context free.
And now look at, $L^C$. I…
user220688
- 509
0
votes
1 answer
Explaining Ultimate Periodicity.
I'm revising for an exam and I've stumbled by Ultimate Periodicity.
The exercise is:
Prove that $A = \left\{ a^{n^2} \mid n \in \Bbb{N} \right\}$ isn't regular.
Can someone explain how we get to an answer with this, an explanation of the…
Marc
- 3
0
votes
1 answer
Proving that $L^*$ is regular if $L$ is
I know that if $L\in REG$ then you can build an automata that accepts $L^*$, but I was wondering if my approach is also good. I thought about showing that
$$L^*=\{\epsilon\} \cup \bigcup_{n\in \mathbb{N}}L^n$$
Where $$L^n=\{\omega_1 \ldots \omega_n…
Yotam
- 453
- 3
- 11
0
votes
1 answer
proof with using pumping lemma
$L=\{0^n\#0^{2n}\mid n\ge 0\}$
Show that this language is iiregular. And now:
Let $p$ will be length of pumping lemma. Given $w=0^p\#0^{2p}=xyz\in L$ such that. Becaues of the fact that $|xy|\le p$ we conclude that $y$ contains only $0s$. So let's…
user220688
- 509
0
votes
1 answer
Regular expression. Proof.
Let $A = \{a,b,c\} $ be an alphabet. Let $\alpha $ be a regular expression. And:
$$ 1) \epsilon \in \alpha \\ 2) a\alpha \subset \alpha \\ 3) b\alpha \subset \alpha $$
Prove, that:
$$(a+b)^* \subset \alpha $$
Intuitively, it is obvious. But I have…
user180834
- 1,453
0
votes
1 answer
Understanding pumping lemma - length $p$ - in connection with other thread
I create this thread in connection with Is the following language $L$ regular?
I would like to show you why I dont understand where I am wrong.
I would like to ask question:
$p$ - length of pumping lemma.
If $L$ is regular then exists $p$ for every…
user220688
- 509
0
votes
0 answers
construct automat for language $Cycle(L)$
We have automat $A$ for language $L$. Construct automat for $Cycle(L)$
where $Cycle(L)=\{uv:vu\in L\}$.
I have a problem with this exercise. Help me, please.
Edit
$A = (Q_A, \Sigma, \delta, q_0, F_A)$- automat for language $L$
$A'$ - copy of automat…
user220688
- 509
0
votes
1 answer
operations which are closest under regularity - other seeing
We have:
$L_1, L_2, $ regular and $L_3$ irreguar. Now:
$L_1\cap L_2$ is regular.
$L_1\cap L_4 = L_3$
Can I say that $L_4$ is irregular ?
The same question about $\cdot, \cup$
user220688
- 509
0
votes
0 answers
Is the following language $L$ regular?
$L=\{ww^Rv\mid v,w\in \{a,b\}^+\}$
Is $L$ regular ?
Edit
Is it ok?
Let $p$ will be length of pumping lemma. Then, $a^pb(a^pb)^Rv\in L$.
When $a^p(a^pb)^Rv = xyz$
$p\ge |y|\ge 1 $
So $a^{p+k}b(a^pb)^Rv$. Because of the fact that $a^{p+k}b(a^pb)^R$…
user220688
- 509
0
votes
1 answer
find automata that accepts following language
Find automata, that accepts following language: $L\subseteq\{0,1\}^* $
$$L=\{w|w\ \text{doesn't contain four 1's in 7 consecutive symbols}\} $$
My only proposition is:
It is only a fragment, but it will be too large to upload it here.
But general…
user220688
- 509
0
votes
1 answer
How can be proved that $L = \lbrace{ a^n b^m \mid n \le m \le 2n \lor m \le n \le 2m \rbrace}$ is not a regular language?
Prove the language is not regular: $L = \lbrace{ a^n b^m \mid n \le m \le 2n \lor m \le n \le 2m \rbrace}$.
I want to use the pumping lemma but I don't know which parts of the string to split up because it seems that the language's condition will…
MeowMixMayne
- 103