Questions tagged [regular-languages]
Questions about properties of the class of regular languages and individual languages.
1,786
questions
-3
votes
2
answers
54
views
Contradiction via pumping lemma
So this is the language that I need to prove is irregular via pumping lemma, however I am completely stuck with this and seeking some advice. The other ones I have done during my tutorial are much ...
user164540
0
votes
2
answers
70
views
How to find prefixes and suffixes for infinite languages? (Automata)
L= {abc}
prefix = {epsilon,a,ab,abc}
suffix = {epsilon,c,bc,abc}
It's easy to find suffixes and prefixes for finite Regular languages. But what will be the ...
1
vote
1
answer
39
views
Is the class of star-free languages just the complement to counter languages within the regular language class?
So I'm kind of confused as I'm not that deep into the algebraic theory of languages.
The wikipedia article states:
Another way to state Schützenberger's theorem is that star-free languages and ...
- 77
1
vote
2
answers
73
views
Union of non regular and regular language
So I have a regular language L and a non-regular language L' and i want to proof wether the union of both is regular or not.
Since I found counterexamples for both cases I want to look at more ...
- 11
0
votes
0
answers
39
views
Union of non-regular and finite language
So i got this problem where should prove whether the union of a non regular language $L$ and a finite Language $L'$ is regular or not.
My Idea was to show that any regular Language $L_r$ cannot be ...
- 11
0
votes
0
answers
31
views
Language of words concatenated with themselves
Let $L$ be a regular language.
Is the language $L_2 = \{ ww | w \in L \}$ context-free? Does it have a name?
- 2,184
0
votes
0
answers
27
views
What is the minimum length word accepted by the product of these simple loop automata?
Let $A_{n} = (aa|aaa|aaaa|\dots |a^{n-2})(a^{n})^* $ where $n \geq 4$ is some natural,and $A_2 = (a^2)^*, A_3 = (a^3)^*$. Clearly every transition is thus labeled by an $a$. From now on let $A_n$ ...
- 495
0
votes
1
answer
61
views
Construct a regular grammar that produces all possible strings of $\Sigma = \{a,b\}$ that do not contain substring 'abba'
I'm really stuck here and do not know what to do. So far, I've constructed a DFA and a regular expression that produces the aforementioned set of strings. Namely, the DFA looks like:
After a lot of ...
0
votes
1
answer
62
views
Is the language regular A2 = {w1w2w3 | w1, w2, w3 ϵ {0, 1}* }? How to prove?
So I think the above language is regular. I tried using pumping lemma but pumping up or down, changes the value of w1 but has no relation with w2 or w3. The resulting string after pumping will also be ...
1
vote
1
answer
78
views
Is (a*b) or (a*b)* star-free?
Here is the proof of a∗ being star-free:
$\Sigma* = \bar{\emptyset} $
$ A∗= \overline{Σ∗(Σ∖A)Σ∗} $
Would this be a proof for $a * b$? :
$ A∗B= \overline{Σ∗(Σ∖A)Σ∗(Σ∖B)} $
For $(A * B )*$ it seems more ...
- 77
0
votes
0
answers
59
views
Minimum number of states in a DFA
Consider the language L given by the regular expression (a + b )*b(a + b) over the alphabet {a, b} . The smallest
number of states needed in a deterministic finite-state automaton (DFA) accepting L is ...
- 1
0
votes
2
answers
92
views
How to prove that $L=\{0^m1^n\;|\; \mathbf{gcd}(m,n)=1\}$ is not regular
The pumping lemma is allowed to be used in this assignment, so I have tried to make $|0^{m+b|y|-|y|}| = |xy^b| = a!, a\ge |y|,a\ge n$ so that $gcd(|0^{m+b|y|-|y|}|,n) \neq 1$.
- 1
0
votes
2
answers
105
views
Why can't I prove that the regular language is closed under concatenation by this way?
I'm reading Michael Sipser's "Introduction to the Theory of Computation", and it says:
THEOREM 1.26
The class of regular languages is closed under the concatenation operation
In the video, ...
2
votes
0
answers
72
views
How to prove this language is irregular without using Myhill-Nerode?
I have this language that I have to prove either regular or irregular.
$$
L_3 = \{mm^rn | m^r \text{ is the reverse of } m,\ m,n \in \{a,b\}^+\}
$$
It's trivial to prove that it is in fact irregular ...
0
votes
1
answer
42
views
Regular expression for binary string containing no instances of 01
In order to enumerate such a regular expression, it's clear one can break down the language into the set $s =\{00,01,10,11\}$ and it is clear that we need to enumerate some expression that avoids the ...
0
votes
1
answer
38
views
How to simplify this regular expression?
How do i prove that the regular expression $$a^*(ba^*)^*$$ is the same as $$(a+b)^*$$. Is there a way to prove this using regular expression identities?
- 1
2
votes
0
answers
34
views
Let $∑$ be an alphabet. Is the set of all DFAs over $∑$ countable?
Let $∑$ be an alphabet. Is the set of all DFAs over $∑$ countable?
I know the set of all regular languages is countable, however, it is impossible to build an injection from the DFAs to the regular ...
- 135
-2
votes
2
answers
38
views
Is the set of all strings over $\Sigma$ countably infinite or not?
Let $\Sigma$ be an alphabet. Is the set of all strings over $\Sigma$ (i.e. $\Sigma^*$) countably infinite or uncountably infinite?
- 1
6
votes
2
answers
980
views
Is the language given by the regex (ab)* star-free?
I was reading about star-free languages recently and a common example of a non-star free language is the one given by (aa)*.
I was wondering if (ab)* would also work (for an alphabet of two symbols ...
user160778
0
votes
2
answers
105
views
What can i say about L1 given that L2, L1L2 and L2L1 are regular?
I found this question in one of our past exams, and I'm not to sure about the correct answer.
I have a language L1 (which i don't know anything about) and another language L2, which is regular, the ...
- 11
0
votes
0
answers
29
views
Prove the language $a^n b^m$ where $m$ is a multiple of $n$ is not regular
Consider the problem
Show $L = \{ a^{n}b^{m}\mid m \text{ es múltiplo de } n \}$ is not regular.
I attempted the following.
Assume $L$ is regular. Then there is a natural number $p \geq 1$ such ...
- 181
0
votes
1
answer
37
views
The language of chains with twice as many $a$s as $b$s is regular?
I am trying to understand the pumping lemma and its instrumentation to show a certain language is not regular. My first attempt was the following problem:
Let $L$ be the language of all words that ...
- 181
0
votes
0
answers
65
views
Regular expression over $\{a, b\}$ for all words with an even number of $a$s, but without consecutive $a$s
I was given the following problem.
Problem. Give a regular expression over $\{a, b\}$ whose language is the set of all words with an even number of $a$s, but without consecutive $a$s. For example, $...
- 181
0
votes
0
answers
38
views
Finding a DFA with same language as given $\epsilon$-NFA
Consider the following automaton.
How does one find a DFA with an equivalent language using an algorithm? In particular, I was requested to use the algorithm described in the answer to this question. ...
- 181
0
votes
0
answers
29
views
Regular expression - Find the equivalence classes of Nerode theorem
Find the equivalence classes of a nerode theorem and use equivalence
classes to construct a reduced DFA for the following language:
$𝑎^+(𝑏+𝜀)𝑐^*$
The answer:
$𝜀,𝑎^+,𝑎^+𝑏𝑐^∗+𝑎^+𝑐^+,(𝑏+𝑐)Σ^...
3
votes
1
answer
455
views
Prove or disprove that two regular languages are equivalent
I have $L_1=\{b^*+b^*a(b+ab^*a)^*ab^*\}$ and $L_2=\{(b^*ab^*a)^*b^*\}$. I want to prove or disprove that they are equivalent.
I have proved that $L_2\subseteq L_1$ and I tried to transform the second ...
1
vote
1
answer
48
views
Prove $\{a^kb^l: 1\leq k\leq l\}$ is not regular using Myhill-Nerode theorem
I have searched quite a few posts here so that I can prove that the language $$L=\{a^kb^l: 1\leq k\leq l\}$$ is not regular (using Myhill-Nerode's theorem). I know that I must find an infinite number ...
0
votes
0
answers
23
views
How does tokenization relates to formalism, lexical grammar, and regular language?
I am reading Bob Nystrom Crafting Compiler's and in the chapter 5 it says this
In the last chapter, the formalism we used for defining the lexical grammar—
the rules for how characters get grouped ...
- 145
0
votes
0
answers
20
views
Theory of computation
I am trying to look answer for this question of toc please help me find the answer.
The question is :
Construct epsilon NFA(Non deterministic finite automata) for regular expression (0+1)*1(0+1)
- 1
0
votes
1
answer
27
views
Is the language of sums of integers regular?
Over the alphabet $\Sigma=\{0,\ldots,9,/\}$, is the following language regular:
$$L=\left\{x/y/z:z=\mathrm{str}\bigl(\mathrm{int}(x)+\mathrm{int}(y)\bigr)\right\}$$
where $\mathrm{str}$ maps an ...
user160778
0
votes
0
answers
23
views
What is the reversal of a regular language useful for?
There is a number of questions on this website about the reversal of regular languages:
Closure under reversal of regular languages: Proof using Automata
Proving that the reversal of a language ...
user160778
3
votes
3
answers
71
views
Can you enumerate the set of all words over a finite alphabet?
Can you enumerate the set of all words over a finite alphabet?
- 31
1
vote
1
answer
40
views
Counting States in the trim automaton for $\cup_{i=1}^{p} L_i \circ L'_i$
Preliminaries. Let $n,m,i,j,p,c \in \mathbb{N}$ with $n,m,i,j,p,c \geq 1$.
Let our alphabet be $\{0,1\}$, with
non-empty languages $ L_i \subseteq \Sigma^n$ and $ L'_i \subseteq \Sigma^m$.
The other ...
- 923
2
votes
1
answer
104
views
Does my finite state automaton accept a string iff it contains the given string as a substring?
I am trying to write down the generalized form of the finite automata which accept strings which contain as a substring an arbitrary string. Here is what I have come up with — I was hoping someone ...
- 125
0
votes
1
answer
30
views
Counting States in the trim automaton for $(L_1 \cup L_2 \cup \ldots \cup L_p) \circ L'$
Preliminaries. Let $n,m,p \in \mathbb{N}$ with $n,m,p > 1$. We allow that $p$
could be large but still bounded by a function of $n$: $p = O(2^n)$. Let our alphabet be $\Sigma = \{0,1\}$, with
non-...
- 923
2
votes
2
answers
77
views
Counting States in the trim automaton for $L\circ L'$
Preliminaries. Let $n,m \in \mathbb{N}$. Let our alphabet be $\Sigma = \{0,1\}$, with non-empty languages $ L \subseteq \Sigma^n$ and $ L' \subseteq \Sigma^m$. We follow the standard definition for ...
- 923
1
vote
1
answer
202
views
Pumpiing Lemma for $0^n1^m0^n$ and $0^{3n}$
To understand the Pumping Lemma, I'm going to prove that the language $L = \{0^n1^m0^n | n,m \geq0\}$ is not regular. I choose string $w = 0^{p/2}1^{p/2}0^{p/2}$, for any even number $p$. Clearly $|w| ...
- 1,519
0
votes
1
answer
88
views
Example of L not regular language that suff(L) is regular
I can't find example of L not regular language that suff(L) is regular
I tried something like this:
{0^n1^n|n>= 0}, but i can't prove that it's suffix is regular
Suff(L) = {x ∈ Σ ∗ | ∃u ∈ Σ ∗ such ...
- 27
0
votes
1
answer
68
views
Check if these 2 regular expressions are equivalent
Check if these 2 regular expressions are equivalent:
$R_1 = (a+b)^*(aa+bb)$
$R_2 = (a+b)^*aa+a^*bb+b^+b$
My approach:
We check if both of these expressions generate the same set of strings. Meaning ...
0
votes
0
answers
123
views
Proving a certain language is regular by constructing a DFA
Let $L$ be a regular language over the alphabet $\sum$, prove that the language defined by $\hat{L} = \{uv \in \sum^* | u^Rv \in L \}$ is regular.
There is guidance in the exercise that instructs us ...
- 229
0
votes
1
answer
109
views
CFG for the given language $L = \{~ a^\ell a^n b^m c^m d^n e^\ell ~|~ \ell,n,m \geq 0 \}$
I am writing this CFG to solve the problem:
$S \to ASBSC$
$A \to aAe ~|~ ε$
$B \to aBd ~|~ ε$
$C \to bcC ~|~ ε$
Is this correct or not?
- 1
0
votes
1
answer
55
views
Let $L$ the language over $\{a,b\}$ of words that contains the same number of occurrences of $a$ and $b$. Which of the following languages is regular?
The options are:
(a) $L \cap a^{\ast}b^{\ast}$
(b) $(L \cap a^{\ast}b^{\ast}) \cup a^{\ast}b^{\ast}$
(c) $L \cup a^{\ast}b^{\ast}$
(d) $(L \cap a^{\ast}b^{\ast}) \cup b^{\ast}a^{\ast}$
My doubt is: We ...
- 305
2
votes
1
answer
142
views
Is there a algorithm to determine if a regular language (expression) is subset of another?
Given two regular languages (fx given by it's accepting regular expression), is there an algorithm to determine if one is a subset of the other?
- 123
1
vote
2
answers
76
views
Deterministic infinite automaton equals a normal DFA?
Assume we have a deterministic infinite automaton. $DIA = (Q, δ, q_0, F)$. Meaning there is no limit to the number of states. I want to prove or disprove that this module equals a normal DFA.
Attempt
...
- 15
0
votes
0
answers
43
views
Desgining NFA under certain constraints
I've got homework to design NFA to accept a set of strings over {a,b,c} in which each string of the language satisfies: "cac" is a substring and "cc" is not a substring and the ...
- 229
0
votes
1
answer
98
views
Designing a DFA with nth character condition for any integer n
Let n be an integer. How can I write finite automata for the language L?
L = {W∈{$0,1,2$}*| The $n_{th}$ from last letter in w is $0$}.
(Please suggest answers; not hints.)
Attempt
Using Regex, I ...
- 15
1
vote
2
answers
130
views
Prove a language created by applying a function on a regular language is regular
Let $L$ be a language over $\Sigma=$ {$a,b,c$}
We define $\forall w\in \Sigma ^{*}$ the function $T$ s.t. $T(w)$ is the word we recieve after removing all instances of $a$ in $w$.
Let $T(L)=${$ T(w) : ...
- 315
2
votes
1
answer
51
views
Is the language with at least as many 0 as 1 on any prefix $\omega$ regular?
Let $L$ be the language of infinite words in $\{0,1\}^\omega$ such that any finite prefix of a word in $L$ has at least as many $0$'s as $1$'s. Is $L$ büchi recognisable?
I think that $L$ is not $\...
- 23
3
votes
1
answer
640
views
Can we transfer every DFA to DFAs with start state having no in edge?
The start state cannot have any "in edge" (an arrow point directly to the start state) and only out edge is possible for the start state. Other states except the start state are free of ...
1
vote
1
answer
92
views
Transform a non-regular language into a regular one using sort
Is there a way where sort turns a non regular language into a regular one.
What I mean by sort is this:
Consider the language $L =$ { $bac, cbca, acbb$}. $sort(L) = $ {$abc, abcc, abbc$} respectively.
...
- 25