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
1
vote
1 answer
proving by construction that language is regular
I had this exercise saying the following:
$$
L =\{w\mid w = w_1xw_2 \land w_1, w_2, x\text{ are words }\land w_1w_2 \in L_1 \land x \in L_2\}
$$
I need to prove that $L$ is regular by defining an automaton for it.
I thought that I'll duplicate $L_1$…
DanielY
- 979
1
vote
0 answers
Proved that a language is regular
Ι need to prove that this language is regular L = {ab^j c^j | j ≥ 0} ∪ {a^i b^ j c^k | i, j, k ≥ 0 and i /= 1}. I have proved that the first track is not regular with Pumping lemma and the second from the link that I post below: is regular language…
psilos
- 21
1
vote
1 answer
Why is the languge of same occurences of ab and ba regular?
Let the language $L = \{ s~|~s\text{ has the same number of "ab"s as "ba"s.} \}$ for the alphabet $\Sigma = \{ a, b \}$. Apparently, $L$ is regular. Why? Wouldn't a machine that recognizes $L$ have to keep a count of either substring?
David Faux
- 3,425
1
vote
2 answers
Prove language is regular
My question is this:
Given a language L, define L' to be the set of all words in L but with the first letter moved to the end of the word.
e.g. if L = {a, ab, abc, abcd, bab} then L' = {a, ba, bca, bcda, abb}
If L is regular, prove that L' is also…
user417638
1
vote
1 answer
Closure under Intersection
I know that if you have two regular languages $L$ And $M$ then they are closed under intersection, that is the intersection is also regular.
However, if you have two non regular languages L and M, is it possible that their intersection is regular?
I…
greenteam
- 333
1
vote
1 answer
Why is my pumping lemma proof misleading?
I am trying to prove whether $L = \{s : s \text{ contains exactly 1 a}\}$ for the alphabet $\Sigma = \{a, b\}$is regular or not using the Pumping Lemma. I think it is regular because I can construct a simple deterministic finite automata that…
John Hoffman
- 2,734
1
vote
2 answers
Merging of two DFAs
I have 3 languages L1, L2 and L3 with
x$\in$L1, y$\in$L2, z$\in$L3 ;
x=$a_{1}a_{2}a_{3}...a_{n}$,
y=$b_{1}b_{2}b_{3}...b_{n}$ and
c=$a_{1}b_{1}a_{2}b_{2}a_{3}b_{3}...a_{n}b_{n}$.
Words of L3 are alternating combinations of x an y , if x and y are…
letter
- 43
1
vote
1 answer
Concatenation of unknown language
$$If \space L_1L_2\space is \space regular, then \space L_2L_1 \space is\space regular$$
Is this statement correct? I can't seem to find any counter example. Besides, what is a good way of tackling this kind of problem?
Louis Kuang
- 293
1
vote
1 answer
How to find if this language is regular or not
I'm currently having trouble with this one:
$$L = \{a^m a^n \mid m, n\text{ is prime}\}$$
I really have no idea. I think it has something to do with Goldbach's conjecture making it impossible to prove, or did I miss something?
V. Mack
- 11
1
vote
1 answer
Using Myhill Nerode
I'm trying to prove to following language is not regular, using Myhill Nerode's theorem:
$L = {a^{n^2}}$
I found this:
$a^n$ (has no equivalence classes to) $a^m$ when n ≠ m because
$a^na^n$ is in L but $a^ma^n$ is not in L, which implies that L…
Steven
- 149
1
vote
1 answer
Regular and not regular based on the value of n
If $L = \{a^nb^n, n \leq 100\}$ is regular, is $L_2 = \{a^nb^n, n > 100\}$ also regular?
$L$ is regular because we can draw an FA(finite automata) for it. It's not possible to draw an FA for $L_2$, right?
stevetronix
- 433
1
vote
0 answers
Check if language $L^2$ is regular
$L=\{w|w\in\{0,1\}^*\wedge \#_1(w)=\#_2(w)\}$, where $\#_a(w)$ denotes number of symbol $a$ in word $w$. Check if $L^2$ is regular.
So idea is: $L^2 \cap 0^*1^*0^*=\{0^n1^{2n}0^n|n\ge 0 \}\notin Reg$
The fact that intersection is not regular is…
user220688
- 509
1
vote
0 answers
$L$ is regular. Prove that $D(L)$ is also regular
I ask you for look at my solution:
$L$ is regular. Prove that $D(L)=\{w|ww^R\in L, w\in\Sigma^*\}$ is also regular.
Idea
I go through states from two places (two fingers). When fingers meet in the same state I accept this word.…
user220688
- 509
1
vote
0 answers
Isn't the set of all literature a regular language?
Let one piece of literature be one string. Let's define our alphabet to be sufficient to represent all literature (e.g. we may need a page-turn character, etc). So, since the collection of current literature is finite, it is a regular language. …
Daniel Donnelly
- 21,342
1
vote
1 answer
construction for proof of regularity of language
$L$ is regular. $L'=\{vw:v\in L, w\notin L\}$
Show that $L'$ is regular.
I ask you for controlling my construction:
$M=(Q,\Sigma,\delta, q_0,F)$ for $L$
$M'=(Q,\Sigma,\delta', (q_0, F') $
$Q'=(\{1\}\times Q) \cup (Q\times…
user220688
- 509