Questions tagged [regular-languages]

Questions about properties of the class of regular languages and individual languages.

Filter by
Sorted by
Tagged with
-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 ...
user avatar
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 ...
Vedant Khandelwal's user avatar
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 ...
Crea Teeth's user avatar
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 ...
Theorynoob's user avatar
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 ...
Theorynoob's user avatar
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?
user1868607's user avatar
  • 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$ ...
Daniel Donnelly's user avatar
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 ...
Nyquist-er's user avatar
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 ...
Crypton99's user avatar
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 ...
Crea Teeth's user avatar
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 ...
Rishi's user avatar
  • 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$.
CXLi's user avatar
  • 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, ...
Nicholas Humphrey's user avatar
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 ...
Edward Shanahan's user avatar
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 ...
bipartite's user avatar
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?
fenhax's user avatar
  • 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 ...
Kantig Shoter's user avatar
-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?
Abhishek's user avatar
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 ...
user avatar
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 ...
pezbecoding's user avatar
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 ...
lafinur's user avatar
  • 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 ...
lafinur's user avatar
  • 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, $...
lafinur's user avatar
  • 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. ...
lafinur's user avatar
  • 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: $𝜀,𝑎^+,𝑎^+𝑏𝑐^∗+𝑎^+𝑐^+,(𝑏+𝑐)Σ^...
Mostfa Mostfa's user avatar
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 ...
Νικολέτα Σεβαστού's user avatar
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 ...
Νικολέτα Σεβαστού's user avatar
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 ...
Finlay Weber's user avatar
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)
Amy's user avatar
  • 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 ...
user avatar
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 ...
user avatar
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?
AAAAA5555555's user avatar
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 ...
ShyPerson's user avatar
  • 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 ...
ZarakshR's user avatar
  • 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-...
ShyPerson's user avatar
  • 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 ...
ShyPerson's user avatar
  • 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| ...
M a m a D's user avatar
  • 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 ...
user1701057's user avatar
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 ...
RandomGuyOnMath's user avatar
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 ...
Yarin's user avatar
  • 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?
Yousaf's user avatar
  • 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 ...
Pratik Hadawale's user avatar
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?
skyking's user avatar
  • 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 ...
NitayStack's user avatar
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 ...
Yarin's user avatar
  • 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 ...
NitayStack's user avatar
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) : ...
Aishgadol's user avatar
  • 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 $\...
Jerry Tao's user avatar
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 ...
Pouya Kafashi's user avatar
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. ...
Anonymous's user avatar

1
2 3 4 5
36