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
Prove that a Language is Non-Regular Using Closure Properties
Use the closure properties of regular languages and a language $B$ known to be non-regular to prove that a language $A$ is not regular.
My understanding is that the closure properties only apply when both languages are regular. So, I'm not sure what…
EggHead
- 667
1
vote
1 answer
If A ≤ B and A is regular, does that imply that B is regular?
In this question, I want to know what the symbol ≤ means. If it denotes reducible, what is the relationship between reduction and regular language? Or, I need an example to illustrate this relationship between two regular language. THX!
Old Panda
- 143
1
vote
1 answer
Show: The set of all languages in which every word has odd length contains non-regular languages.
Prove that $\xi = \text{The set of all languages in which every word has odd length}$ over $\Sigma = \{a,b\}$ contains non-regular languages.
So I offered this proof and I really think that it has many holes (and I am not even certain if it is…
TheNotMe
- 4,841
1
vote
3 answers
Can one prove that a language is regular without having a regular expression?
I was wondering if one could prove that a language is regular without showing a DFA/NFA or a regular expression that expresses it.
For example: $L = \{w \in \Sigma^* : w \text{ has at least two identical letters} \}$
TheNotMe
- 4,841
1
vote
2 answers
If given a regular language, how can we prove that a sub-language is regular?
This question has been quite confusing me.
$\sum = \{a,b,c\}, L \text{ is a regular language}$ and we have to prove that $L^{'} = \{w \in L : w\text{ containts at least one c} \}$ is regular.
What are the steps of the proof? What methods can we use?…
TheNotMe
- 4,841
1
vote
0 answers
regular languages and suffixes
Let $\Sigma$ be a finite alphabet. For a language $L \subseteq\Sigma^*$ we define:
$$Suff(L)= \left\{x\in\Sigma^*| \exists u \in \Sigma^*, u\cdot x \in L\right\}$$
Show an example of a language $L$ that is not regular for which $Suff(L)$ is…
BridonElden
- 47
- 5
1
vote
1 answer
Proving a language is not regular using pumping lemma
I had an exam today and the professor gave us the following problem:
Let $L = \{a^nb^m : n|2m \}$. Prove that $L$ is not regular.
Ok this sounds easy. Here is my solution: Assume opposite -- $L$ is regular. Then by the pumping lemma there exist…
user2564944
- 13
1
vote
1 answer
Pumping Lemma Proof for $ww$
The proof of language $F = \{ww\mid w ∈ \{0,1\}^*\}$ is not a regular language using pumping lemma most of the solutions i found uses the string $0^p10^p1$. I understand the proof using that. But in Michael Sipser's Introduction to the Theory of…
Learner
- 13
1
vote
0 answers
Proving that language is regular or not regular
Let $L$ be a regular language. Prove that:
$L_{+--}=\left\{w: \exists_u |u|=2|w| \wedge wu\in L\right\}$
$L_{++-}=\left\{w: \exists_u 2|u|=|w| \wedge wu\in L \right\}$
$L_{-+-}=\left\{w:\exists_{u,v} |u|=|w|=|v| \wedge uwv\in L\right\}$
are…
xan
- 2,053
1
vote
1 answer
Is language of binary representations regular?
Let $bin(n)$ denote binary representation of an integer $n$. Let $L=\left\{bin(n^2):n\in\mathbb{N}\right\}$. Is $L$ a regular language?
xan
- 2,053
1
vote
1 answer
Is it true that a language is regular?
Is it true that for every regular language $L \subseteq \{0,1\}^*$, language
$\big\{ w^{|w|} \big| w \in L \big\}$
is regular?
I don't know how to prove that.Could you give me a hint?
Thank you
emilsim
- 13
1
vote
1 answer
How to prove that given language is not regular?
Prove that
$$L=\left\{uvvw\mid u,v,w \in \{a,b,c\}^*\text{ and }v\ne\varepsilon\right\}$$
is not regular a regular language.
A. Johannson
- 37
1
vote
1 answer
Construct a Non-deterministic Finite State Automaton (NFA)
Construct a Non-deterministic Finite State Automaton (NFA) M with minimum number of states for the set of strings over {0, 1} such that each 0 in the string is immediately followed by a 1.
The image below is the NFA i've drawn. However i do not know…
1
vote
1 answer
Question about infinite union of non-regular languages
If none of the languages $L_1$,$L_2$,... is regular,
and $L_i \subseteq L_{i+1}$ for each i, is $\bigcup_{n=1}^\infty L_i$ regular?
I guess the answer is no for any given languages, but I cannot formulate my arguments properly.
Thank you for the…
Evgenii.Balai
- 299
1
vote
1 answer
Proving that a language is not regular using pumping lemma
I'm asked to like come up with a language that is not regular but im unsure how to. Could someone explain how to come up with a simple one so it would be easy to prove it later?
Tinler
- 1,061