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
How to read formal definition of a language.
I need to give nondeterministic finite automata for the following language:
$$
L = \{w \in \{a, b\}^∗ \mid w \in ba^*a \cup ((a \cup bb)^*ab^*)\}
$$
The * above are Kleene Stars
I'm having trouble reading this, I think its:
Language $L$ is a set of…
Adrian M
- 103
0
votes
0 answers
Why is the singleton language {x} regular?
So in most definitions of a regular language, it states that Ø and {x} are regular. I am curious as to why the singleton language {x} is regular, like what proof or reasoning for it to be a regular language? This is important to me, because I am…
0
votes
1 answer
Myhill Nerode to prove $0^*1^*$ is regular?
For the language $L=0^*1^*$, I want to use the Myhill-Nerode theorem to prove it is regular.
I'm trying to first list out the subsets of the alphabet but don't understand how I can use them to make my proof:
$A1 = L$
$A2 = \{w\mid \text{w is not in…
MakinCode
- 11
0
votes
2 answers
following languages regular or not?
Please help me determine if those languages are regular or not. If not, I'll be glad to get a direction to prove it by contraditiction of the pumping lemma:
$L = \{a^n\mathord{*} a^m \mid m \equiv n \pmod 3\}$
$L = \{w \in \{0,1\}^*\mid…
DanielY
- 979
0
votes
1 answer
Regular Language : $\{a^m b^n \mid mn \ge 10\}$
I am little bit confuse here about below language is it regular language
$$ L= \{a^m b^n \mid mn \ge 10 \}.
$$
Nishant
- 105
0
votes
1 answer
Given a regular language, show another language is regular
I was hoping someone could help me with this question, since I'm having trouble determining what approach to take.
Let $L \subseteq \{0,1\}^*$ be a regular language. Show the language $\{w \in \{0,1\}^* | 1w \in L\}$ is also regular.
My idea is…
CrossGuard
- 297
0
votes
1 answer
In the context of regular languages is Ø* = Ø?
In the context of regular expressions is Ø* = Ø? and why?
j doe
- 3
0
votes
1 answer
Show that $L$ is regular
If there is a regular language $M$ over $\Sigma = \{0,1\}$, then show that language
$$L = \{x : x\in M \text{ and $x$ ends in 10}\}$$
is regular as well. I'm thinking of closure under Union or Difference but cannot connect the dots.
Really…
heevmo
- 3
0
votes
1 answer
Programming Languages: Pumping theorem(regular lang) walk through
so I'm trying to figure out pumping theorem for regular languages. Here is an example from class. I'm going to label each line and ask questions about the proof.
Problem:
Let language $L = \{a^m b^n c^q \mid m>n\text{ or }m>q\text{ or }n>q\}$.…
user369064
- 21
0
votes
2 answers
A Recursively Defined Set of Strings
Describe the strings in the set $S$ of strings over the alphabet $\Sigma = \{a,b,c\}$ which are defined recursively by:
(1) $a$ is in $S$, and
(2) if $x$ is in $S$, then $ax$ is in S, $xb$ is in $S$ and $xc$ is in $S$.
So far I have in $S$:
a, aa,…
0
votes
1 answer
If $L_1 \cup L_2$ is regular and $L_1$ is a finite language, then $L_2$ is regular
A regular language (also called a rational language) is a formal language that can be expressed using a regular expression.
So, Assume that we have a regular language like $L=L_1 \cup L_2$ and we know that $L_1$ is a finite language. How can we…
Arman Malekzadeh
- 4,108
0
votes
3 answers
The family of regular languages
Is the family of regular languages closed under countable infinite unions?
If so prove it, If not give a counterexample.
zxccxz
- 79
0
votes
1 answer
Is the family of regular languages closed under the operation of set difference?
Prove that the family of regular languages is closed under the operation of set difference.
(I tried coming up with an NFA that will recognize the new language, but I get stuck with defining the transition function.)
zxccxz
- 79
0
votes
1 answer
0
votes
4 answers
Regularity of the language
$L= \{ xy \mid x,y \in \{a,b\}^* \}$ is not a regular language. But would it make a difference if we added another constraint that $|x|=|y|$. Would this enforce the condition of finiteness on the language?
Richa Sachdev
- 207