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
$L$ is regular. Show that $Root(L) $ is also regular
Let $Root(L)=\{w \mid \exists {n\in \mathbb{N}} \text{ such that } w^n\in L\}$.
How to deal with it ? I tried think about modifications connected with automat for $L$, but it failed. Help me, please.
user220688
- 509
1
vote
1 answer
show that language $L'$ is regular (given $L$ regular)
Let $L$ be a regular language. Show that $L'=\{x \mid\exists_{y,z} xyz\in L \text{ and }|x|=|y|=|z|\}$ is also regular.
Firstly I show my idea. When you accept it I will try to formalize it.
Every automat can have exactly one accept state. So let…
user220688
- 509
1
vote
1 answer
Regular language. Proof
Let $L$ be regular language over $\{0,1\}$. Prove that $L'$ is also regular:
$$L' = \{ w | w \in L \mbox{ and among words of length |w|, w is the least in lexicographic order.} \}$$
To explain, for example, if $ L = \{ 10001, 00001, 001,000\}$ then…
user180834
- 1,453
1
vote
0 answers
prove that language is regular (other language is regular)
Let $L$ is regular. Prove that $L'$ is regular.
$ L'=\{uv: u\cdot rev(v)\in L\}$
$rev(v)=v^{-1}$
Idea:
$L^{-1}$ is regular and recognized by $R$, and $L$ by $M$. Let's assume that $M$ is NFA such that there is only one accepter.
$q\in M$ is…
user220688
- 509
1
vote
1 answer
Prove that if $L$ is regular then $f(L)$ is regular
Prove that if $L$ is regular then $f(L)$ is regular.
$$f(L)=\{w: \text{every prefix of $w$ of odd length $\in$ L } \}$$
So my attemption is:
Let $M= (Q, \Sigma, \delta, q_0,F) $ will be DFA recognizing $L$
Let construct $M'=(Q', \Sigma,\delta',…
user220688
- 509
1
vote
0 answers
Prove that language is regular given other regular language
Let $L\subseteq A^*$ be regular. Prove that $L'$ is regular where
$L' = \{vw \mid \exists u\in A^*\ vuw \in L\wedge |u|=|w|+|v|\}$
Help me please. It is very hard for me, I don't know how to start. This type of exercises is extremely hard.
user220688
- 509
0
votes
1 answer
Is this language regular? $\{0^n 1^m \mid m \ne n\}$, I don't understand the direct proof by pumping length
There is a direct way to prove it: If $p$ is the pumping length and we take the string $s = 0^{(p)}1^{(p+p!)}$, then no matter what the decomposition $s = xyz$ is the string $xy^{(1+p!/|y|)}z$ will equal $0^{(p+p!)}1^{(p+p!)}$ which is not in the…
0
votes
1 answer
find a regular expression
find a regular expression for w such that it does not contain $ aab $ , where w is the strings of $a$'s and $b$'s .
ans: I know how to draw the same question with $ aab $ , but cant understand how to proceed for this question.
xxx
- 69
0
votes
1 answer
Check if it is regular language
I have a language $L = \{ a^i b^j c^k \mid i \geq 1 \land j \geq 1 \land k \geq 1 \land (i \neq j
\lor j \neq k) \}$
and how to check if it is regular language? I tried using pumping lemma for regular languages, but I have no idea which word I…
Mopeq
- 1
0
votes
2 answers
Prove that a language is not regular.
I want to ask how to prove the following language is not regular using closure properties. I tried to use pumping lemma but I find the proof itself shaky. I'd appreciate if you can help.
The language is $ L = \{0^{i}1^j0^k, where\ i+j \neq k\}$.…
y123liu
- 117
0
votes
1 answer
How can I show that the language is regular using the closure properties?
How can I show that the language $L=\{ w \in \{a,b\}^*: \text{ the word w contains an even number of a and an odd number of b} \}$ is regular using the closure properties?
Mary Star
- 13,956
0
votes
1 answer
Is it necessary that X is also regular?
Given that $L$ is a regular language and $X \subseteq L$,does $X$ have to be also regular?
evinda
- 7,823
0
votes
1 answer
Show that the language is regular modifying the DFA
Let L be a regular language. How can I show that the language $\text{Suffix}(L)=\{w
\in \Sigma^* \mid \text{ there is a $x \in \Sigma^*$ so that }xw \in L\}$ is also regular? How can I modify the DFA of $L$ so that it accepts $\text{Suffix}(L)$.
Mary Star
- 13,956
0
votes
1 answer
Show that the language is regular without a DFA
How can I show that the language {$w \epsilon$ {$0,1$}$^{*}:$ the word $w$ contains neither the (sub)string $000$ nor $11$} is regular without using a DFA? (Using the closure properties)
Mary Star
- 13,956
0
votes
1 answer
Pumping lemma-regular language
Show that the language $L = \{w \mid w \in \{a,b\}^{*}\}$ is not regular by using the following version of Pumping Lemma:
Let $L$ be the language, which has an infinite number of words, then there are words $x,y,z \in \Sigma ^{*}$, so that $|xz|…
evinda
- 7,823