As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [regular-languages]

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

1,761 questions
Filter by
Sorted by
Tagged with
18 views

### Pumping lemma about regular language

I need to test if this language is regular using pumping lemma L = {x ∈ {0,1}* | ∃y ∈ {0,1}* . xxx=yy} So, this is the language of strings with three equal chars ...
15 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)
22 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 ...
18 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 ...
38 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
36 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 ...
62 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 ...
24 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-...
69 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
51 views

39 views

53 views

### Is pumping lemma not applicable for every 'long enough' string in the language?

I recently learnt that a subset of a regular set may not be regular. This is causing me confusion as I imagined if a set is regular then every string longer than $p$ can be pumped in the language. So ...
1 vote
33 views

### Is it true that $R.L^* + L^* = R + L^*$?

I am trying to solve a problem to show equivalence between two regular expressions, and simplifying one of them I got $R.L^* + L^*$ in the end which I am not sure how to simplify further. I want to ...
47 views

### Algorithm to determine the regularity of a language

According to the answer provided by Janoma, there are several methods to determine the regularity of a language. Theorem Let L ⊆ Σ∗. The following conditions are equivalent: L is generated by a ...
33 views

### Pumping length of (a+b)(a+b)*

I'm trying to figure out the pumping length of (a+b)(a+b)* From what I understand, this means that there is some A or B followed by any number of either A's or B's e.g ABBBB or AAAAA but AAAABA ...
1 vote
26 views

### Confusion regarding FLEX(regular expressions)

I am building an analyzer that takes in text and numbers the lines; taking in hello how are you i'm fine thanks as input and using the code: ...
61 views

### What is a regular expression that describes whether an integer w is a multiple of 6?

Let's say we are looking at the decimal language $L_6$ where $$\Sigma = \{ 0,1,2,3,4,5,6,7,8,9 \}$$ and $L_6$ accepts an integer w if w is a multiple of 6. I'm trying to find the regular expression ...
1 vote
106 views

43 views

52 views

### If $L_1 \cup L_2 \in RE$ does it implicate that at least one of them is also in RE?

This was one of my exam questions and the answer is apparently no. Can someone explain why because I don't understand.
1 vote
93 views