# Questions tagged [regular-languages]

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

1,846 questions
Filter by
Sorted by
Tagged with
79 views

### $L'=\left \{w : w\cdot Drop_a(w)\in L \right \}$ is a regular language

$\Sigma=\left \{ a,b,c \right \}$. For a string $w\in \Sigma^*$, $Drop_a(w)$ is the string $w$ after we remove all occurrences of "a" from it. The question asks to show that if $L$ is a ...
• 147
1 vote
51 views

### Creating a DFA where the string should start with b and the length is 3

I'm new to automata and in my first exercise I have to construct a DFA that starts with 'b' and length=3. Two symbols (a,b). To my understanding, there are 4 possibilities {baa,bab,bba,bbb} I have ...
• 21
47 views

### Do all regular languages have a backwards deterministic FSM with one initial state and no $\varepsilon$-transitions?

There's been a question about an algorithm converting an arbitrary FSM into a backwards deterministic automaton without $\varepsilon$-transitions and a single initial state. As commenters pointed out, ...
• 1,467
133 views

### Is there an algorithm to turn any finite automata into a backwards deterministic one, with no $\epsilon$ transitions, and only one initial state?

An automaton is backwards deterministic if, for all states q, p, for all symbols a: $$(\delta(q, a) = \delta(p, a)) \implies p = q$$ (I think the right translation is backwards deterministic, but ...
• 53
40 views

### FSA for 'closure' of a language; how to represent?

Is my interpretation of this correct? I want to represent a regular language, L(B) as L(A*) where L(A*) represents the closure of L(B), as a DFA. In order to do so, would I draw a new edge from the ...
• 87
55 views

### How is L = a^2n regular if it doesn't pass the pigeon-hole principle test?

I understand that this topic has been discussed, and I have reviewed numerous posts about it on stack overflow. However, my question remains unresolved. Specifically, I am seeking clarification on the ...
• 11
1 vote
55 views

### Splitting strings in pumping lemma for regular language

I was recently reading the book Introduction to the Theory of Computation, Second Edition by Michael Sipser, and encountered the following example: Let $F=\{ww\ |\ w\in \{0, 1\}^*\}$. We show that $F$...
• 13
49 views

### Is garbage state necessary in DFA that enforces a particular input combination?

If I have the regex 1(0+1)* for example, then should my DFA have an arrow leading away from the starting state for when the first input is 0? I see that this regex ...
• 87
221 views

### Is it possible to have intersection of L1 and L2 DFA contain states with no input edge?

I am doing a HW problem where I have L1 and L2. I did the product construction method to produce all the new states of the DFA representing L1 and L2 (the number of states in L1 times the number of ...
• 87
30 views

### Question about a grammar who generates $(0+1)^*$

On a test from my Automata theory class of last year, I have seen an excercise that gives the free context grammar $G$ with the following rules: $$S \rightarrow 0S1 | S0 | 1S | \varepsilon$$ and asks ...
116 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
83 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 ...
• 113
1 vote
48 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
48 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 ...
• 49
109 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 ...
• 139
51 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 ...
37 views

• 147
72 views

• 57
### 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}$?