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
1 answer
Show that the language is regular
Given a regular language L on the input alphabet Σ, and X a subset of Σ*, show that the language {$w$:$w$ $\epsilon$ L, there is a x $\epsilon$ X so that $wx$ $\epsilon$ L} is also regular. Could you help me showing this, because I got stuck..
Mary Star
- 13,956
0
votes
1 answer
Prove that class of regular languages is closed on operation
Let's have an operation $$\odot(L)=\{w\in L \; | \; |w|=2k \land k>0\}$$Show that result of this operation will be regular.
PS: It's not homework, it's from last year's exam.
Noturab
- 497
0
votes
1 answer
The pumping theorem and regular language
I have this problem:
$L_0 = L(a^*bba^*)$, the language of the regular expression $a^*bba^*$
$L_1 = \{uu \mid u \in L_0 \}$
Is $L_1$ a regular language?
I know that I should use the pumping theorem for this, but I don't know how to use it.
I assume…
rablentain
- 645
0
votes
2 answers
Are those two regular languages the same?
Given an alphabet of {a,b} where Na denotes the number of occurrences of a, and Nb the number of occurrences of b:
1) L1 = {xy|Na(x)=Nb(y)}
2) L2 = {w|Na(w) is even, Nb(w) is even}
Wouldn't a single DFA with four states and using mod be able to…
0
votes
0 answers
Trying to disprove that if Prefix(L) is regular then L is regular
I've thought of using $L=${$a^{2^n}, \forall n \in \mathbb{N}$} and then $prefix(L)=\Sigma ^{*}$.
which we know $\Sigma^{*}$ is regular. however, $L$ is not regular.
is this a correct solution?
Aishgadol
- 389
0
votes
1 answer
Need help with this regular language proof
I'm trying to prove that if $L$ is regular, then $L_S$ is regular as well.
$L_s$ = {$x$ | $∃$ $w ∈ Σ^*$ such that $wx∈L$}
I know one way to do this would be to create an NFA that accepts $L$, then modify it so it accepts $L_S$ as well.
Jose
- 253
0
votes
1 answer
Regular language: what is the Union of the iteration of 0's with the iteration of 1's
I'm taking the Edx Stanford compiler course and it shows
$0*$ + $1*$ = $(0^i | i >= 0)$ u $(1^i | i >= 0)$
Sorry screen readers but in case my mathjax is illegible.
In the second line it shows what $1*$, ie. the iteration of 1 looks like:
"", 1,…
mLstudent33
- 224
0
votes
0 answers
Finding an infinite language with finite equivalence classes
Let $\Sigma$ be an alphabet and let $L$ be a language on $\Sigma$. If it is known that all the equivalence classes of $R_L$ are finite, is $L$ regular? If definitely yes, prove. If definitely no, prove. If it cannot be determined give an example to…
CforLinux
- 393
0
votes
0 answers
How are all words over S in the language in this question?
Let $S = \{a, b\}$ and let $X= \{w \mid \text{$w$ is a word over the alphabet $S$}\}$. For each language given below, list (if you can) two words which are in the language, and two words which are not in. (In either case, if there are no two such…
Jade
- 21
0
votes
1 answer
$L_1$ is regular and $L_2$ is not. What can i say about their union or intersection?
Given $L_1$ is a regular language and $L_2$ is a non-regular language.
$\Longrightarrow$ then $L_1\cap L_2$ (the intersection) is non-regular OR $L_1\cup L_2$ (the union) is non-regular.
Is it true or false?
Can you give an example/proof?
ryden
- 583
0
votes
1 answer
Prove regular expressions are equal: $0^*1(1 + 00^*1)^*$ is $(0 + 1)^*1$
I tried:
$0^*1(1 + 00^*1)^* = 0^*1(1^* (00^*1)^*)^*$
but after that I'm not sure how to get further. I can definitely see that this expression always ends with 1 and that's what $(0 + 1)^*1$ but I don't see a rigorous chain of arguments to prove…
sprajagopal
- 622
- 1
- 5
- 20
0
votes
1 answer
Theorical question about union of two regular languages
I have seen the propity of $L_1\cup L_2$ is a regular language if $L_1$ & $L_2$ are regular languages.
But it works backwards? If i have a regular language L, always exist two others regular languages that together makes L?
Can i have a…
André Kuljis
- 33
0
votes
1 answer
Algorithm for checking if regular language has given property
Give an algorithm that will decide (in any finite time) if given regular language $L$ (given by some regular expression) has given property:
$$\forall_{x\in L} \exists_{y\in L} \left( \left(x\neq y\right) \wedge \left(x\text{ is a substring of }…
xan
- 2,053
0
votes
2 answers
Is the given Language $L$ regular?
$L = \{ a^nb^m : m + n\text{ is divisible by }3 ; m,n\ge 0\}$. Is this language regular, and if so, what is the regular expression?
Sarthak Gupta
- 103
0
votes
1 answer
difference between $( a\cup b)^{*}$ and $(a+b)^{*}$
difference between $(a\cup b)^{*}$ and $(a+b)^{*}$, i tried to search for concrete answer but nowherebi could find it? are they both same in terms of regular expression
Aayush Neupane
- 101