# Questions tagged [regular-languages]

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

1,837 questions
Filter by
Sorted by
Tagged with
41 views

### Why $(a+b)^* = (a^*b)^* a^*$

I have seen on a book that for regular expressions it holds the equality $(a+b)^* = (a^*b)^* a^*$ but I am not seeing why. It is clear that the language generated by $(a+b)^*$ contains $(a^*b)^* a^*$, ...
1 vote
37 views

### How to formally prove that any regular expression can be written as a finite combination of base cases and operations?

In Michael Sipser's book, "Introduction to the Theory of Computation," regular expressions are defined as follows: Based on this definition, how can I formally prove that any regular ...
• 111
1 vote
37 views

### Kleene star of any unary language is regular

I want to prove: Let $L \subseteq \Sigma^*$. If $\Sigma=\{a\}$, then $L^*$ is regular. I found this answer: Kleene star of an infinite unary language always yields a regular language. But I do not ...
• 23
1 vote
30 views

### How to demonstrate that the intersection of a context-free and a regular language is context-free?

I'm working on a theoretical computer science exercise and need some help with solving it. Here's the task: Task: Let $C$ be a context-free language and $R$ a regular language. Show that $C \cap R$ is ...
• 29
105 views

### Number of a, b and c is even

The language of strings over $a$, $b$ and $c$ such that the number of $a$ is even, the number of $b$ is even and the number of $c$ is even is clearly regular (it is easy to construct a FA or a RE for ...
• 141
50 views

### Help regarding a proof in which i am able to prove a regular language $(a(a+b)*)$ as irregular using pumping lemma

I have a regular language $a(a+b)^*$ to which i applied pumping lemma. Let the pumping length be $'p'$ and the example string be $$w=a(a+b)^{p-1}$$. The string satisfies the condition that it is at ...
28 views

• 71
63 views

• 57
42 views

### How is $|xy^{2}z| < 2^{p+1}$ (Pumping Lemma application)

In the Question here it is said that $|xy^2z|<2^{p+1}$ Considering that $|x| = 0$ and $|z| = 0$, y consists of $2^{p}$. It's probably trivial, but how do I see, that $|xy^2z| < 2^{p+1}$?
• 57
590 views

### What does empty string ε actually mean?

I came across this weird expression while learning about regular expressions. $R^+ \cup \varepsilon = R^*$ why does doing union with an empty string makes this regex go from 1 or more to 0 or more?
• 71
1 vote
64 views

### Why can't we prove closure under concatenation using DFA?

I can't understand why do we have to use NFA to prove that concatenation operation is closed. According to sisper's book it says that we can't determine where to split the string, i.e. where to ...
• 71
54 views

### Is the $L'$ regular or not? [duplicate]

Suppose $L$ is regular and we define $L'=\{x:\exists y\in L \wedge \text{ y be a subsequence of x}\}$. Could we conclude that $L'$ is regular or not? I think it's not regular because if $L=a^*b^*c^*$ ...
• 1,942
42 views

### Prove that if $L \subseteq b^*$ isn't regular then $M = a^+L \cup b^*$ isn't regular

There is an exercise in a book about finite automata that I couldn't solve: Prove that if $L \subseteq b^*$ isn't regular then $M = a^+L \cup b^*$ isn't regular either, using the fact that REG is ...
• 1,222
1 vote
28 views

### In regular language inference, how is the observation table kept consistent?

I am trying to understand the background literature on regular language inference in the TTT paper ("The TTT Algorithm: A Redundancy-Free Approach to Active Automata Learning" by Isberner, ...
1k views

### Proof that a union of two non-regular languages may be regular

Let $L_1 = \{ a^{n}b^{m} \mid n > m > 0 \}$. Describe a non-regular language $L_2$ such that $L_3 = L_1 \cup L_2$ is regular and $L_3 ≠ A^{*}$ (where $A = \{ a, b \}$) From the trace, I cannot ...
• 63
59 views

### Determining the language of a DFA

I've tried quite a large amount of examples, starting from 1 bit all the way up to 5 bits yet I couldn't put my finger on any recurring pattern of words that are accepted. the DFA is as such: The ...
• 355
1 vote
69 views

### Proving the set $R$ is finite

Suppose $L$ is a regular language. Let $R\subseteq L$ be a language with maximal size such that for each $x,y\in R$ neither $x$ be a substring of $y$ after removing a substring from $y$ nor $y$ ...
• 1,942
Let $B$ and $C$ be two languages on $A = \{a,b\}$: $B = \{ w \mid w \text{ has the same number of }a\text{ and }b\text{ symbols}\}$ $C = \{ a^n b^m \mid n,m \ge 0\}$ Describe $B \cap C$ and determine ...