# Questions tagged [regular-languages]

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

1,786 questions
Filter by
Sorted by
Tagged with
54 views

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 ... 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
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 ...
1 vote
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 ...
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 ...
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?
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$ ...
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 ...
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
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 ...
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 ...
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$.
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, ...
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 ...
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 ...
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?
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 ...
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?
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 ... 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 ...
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 ...
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 ...
65 views

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
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 ...
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 ...
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)
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 ... 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 ... 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?
1 vote
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 ...
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 ...
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-...
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 ...
1 vote