# Questions tagged [regular-expressions]

Questions about regular expressions, a formalism to describe regular languages.

847 questions
Filter by
Sorted by
Tagged with
1 vote
602 views

### Converting Regular Expression to Finite Automata

I am studying "Theory of Computation" by Michael Sipser. I am studying the section where he teaches how to convert "RE to FA". He uses empty transitions for union, concat and star, ...
1 vote
298 views

### Converting Deterministic Finite Automata to Regular Expression

I am reading Michael Sipser's "Theory of Computation". In one of the proofs he talks about converting "DFA to Regular Expression" and he talks about "GNFAs". I understand ...
1 vote
1k views

### Construct a regular expression for the set of strings over {a, b} that contain an odd number of a's and at most four b's

Construct a regular expression for the set of strings over {a, b} that contain an odd number of a's and at most four b's. So far, I have $(aa)^*a((b+\varepsilon)(aa)^*)^4$, but I don't think this ...
• 11
5k views

### Proving Equivalence of Two Regular Expressions

Consider the regular expressions $(1+01)^*(0+\epsilon)$ $(1^*011^*)^*(0+\epsilon) + 1^*(0+\epsilon)$, where $\epsilon$ is the empty string. I need to determine if these expressions are equivalent. ...
• 257
196 views

### Regular Expression for $L = \{w \mid w\in \{a,b\}^*\text{ and }n_a(w) \equiv 1 \bmod 3\}$

Here, $Σ=\{a,b\}$ The number of $a$ can be $1, 4, 7, 10.....$, also $a$ can be placed anywhere. Find Regular Expression for $L = \{w \mid w\in \{a,b\}^*\text{ and }n_a(w) \equiv 1 \bmod 3\}$ How can ...
93 views

### What is the formalism used to describe optional arguments called?

Most command line tools have an usage described by using square brackets for optional parts and just writing out required parts (like in regexes) for example: foo [opt1[opt2...]] req1 req2 [opt3...] ...
1 vote
43 views

### How does + symbol works in regular expression?

What's the difference between $a^*+b^*$ and $(a+b)^*$? I was going through this question. So according to the question-: (a+b)* generates $\in$, a,b,ab,ba,aa,ba,... whereas a*+b* generates $\in$, ...
• 13
4k views

### Regular expression for all strings not containing $aba$

This is my first post here. We are currently studying regular expressions, and I have been tasked to write a regular expression for the language of all words which do not contain the substring $aba$, ...
• 177
1 vote
126 views

I once had an idea for a multithreaded regex engine. The first method that occured to me (there may be other ways to do it that I haven't thought of) was to split up the string being matched against ...
• 133
169 views

### Prove that the problem of REGEX producing strings with 111 as substring is decidable

I have been given the following problem and was wondering if my solution is correct (taken from the textbook exercise in the book Introduction to the Theory of Computation by Martin Sipser): Given <...
1 vote
418 views

### Showing that for every NFA with n states, there is a regular expression of length $O(2^n)$

Consider the idea of an extended non-deterministic automation, where transitions can be labelled by regular expressions and not simply by symbols of the input alphabet or $\epsilon$. Such an automaton ...
• 443
1 vote
31 views

### Construct a regular expression for a specified language

Let $\Sigma = \{a, b\}$ I need to find a regular expression for this language: The language where the number of $a$'s and $b$'s is equal and for every prefix of a word the absolute value of the ...
• 261
68 views

### Finding an algorithm that decides given 2 regular expressions $E_1$ and $E_2$ and a non-negative integer $k$, whether $|L(E_1) \backslash L(E_2)| = k$

Find an algorithm that decides, given 2 regular expressions $E_1$ and $E_2$ and a non-negative integer $k$, whether $|L(E_1) \backslash L(E_2)| = k$. I know that regular expressions are closed under ...
• 443
164 views

### What is the language of this simple DFA with 4 states?

I wanted to say that the language is the set of strings that end with "101" but unfortunately it does not work. Take for example "110101", which is not accept by the dfa.
132 views

### having trouble understanding the proof of regular expression identities $(u + v)^* = (u^*v)^*u^*$

I am having trouble understanding the proof given below: \begin{align} (u \cup v)^* &= (u^* \cup v)^* \\ &= u^*(u \cup v)^* = (u\cup vu^*)^* \\ &= (u^*v^*)^* = u^*(vu^*)^* \\ &= (u^*v)...
1 vote
446 views

### Regular Expression for Grammar = ({X, Y, Z}, {a, b}, X, {X → aY | bZ, Y → b | bZ, Z → a | aY})

2nd year college student here, I have trouble finding for the regular expression for that grammar, any help would help :D Regular Language of the grammar: X → aY → ab X → bZ → ba X → aY → abZ → aba  X ...
1 vote
508 views

### Regular expressions and equivalence classes

I need a little help regarding this problem: Let L = {w ∈ {0, 1} ∗ : w has an even number of 0s and the last character of w is a 1}. Give the equivalence classes of the relation ≡L using regular ...
• 13
121 views

### Every non-regular language has a subset which is a regular language?

Could anyone give me a counterexample so as to understand the proof? Thanks in advance
• 111
84 views

### Translating weighted regular expressions with the complement operator to weighted deterministic automata

I want to implement regexp search via translation to deterministic automata, as a toy project. TLDR: how to combine the extended regular expressions with the weighted regular expressions, with the ...
• 201
215 views

### Is this language regular or non-regular : {ww | w ∈ {a,b}* } ∩ {a}*

I think it's a regular language but I can't find a DFA or a regular expression. Would anyone know how to help me?
• 111
1 vote
817 views

### Regular expression of binary strings not containing $1011$ or $1101$ as substring

I tried to solve by explicitly writing strings of length $2$, $3$ and $4$ (other than $1011$ and $1101$), but it creates a lengthy regular expression. Can someone suggests underlying pattern that ...
• 111
1 vote
260 views

### How do I find the regular expression for- All binary numbers greater than 110011

I am trying to solve a problem set to practice for an exam. How can I approach questions like these ? Is there a way to verify solutions or is it just trial and error ?
• 111
95 views

### What could be possible NFA for the RegEx "a?"

I am trying to use the Thompson's method to draw an NFA for a RegEx given by: $(a+b|c?)c$ I am wondering if I should deconstruct the RegEx as - Concatenation of $a+$, $(b|c?)$ together with $c$ OR ...
734 views

### Convert ((ba ∪ ab)∗ ∪ b)* to NFA

How do I simplify this $((ba \cup ab)^∗ \cup b)^*$? I can draw the NFA for the '$ba$', '$ab$' and '$b$' term but when it comes to linking the '$ba \cup ab$' to the '$)^∗ \cup b)^*$' i am unsure how ...
25 views

### How ot prove a language is regular using L′ = {ab(^i)c)^i) | i ≥ 0 [duplicate]

I have the following language L = {a(^i)b(^j)c(^k) | i, j, k ≥ 0, and, if i = 1 then j = k} . How do I use the fact that L′ = {ab(^i)c)^i) | i ≥ 0 to prove that is it not regular? I am given a hint ...
183 views

### Lexical analysis on a series of tokens given regexes

I am to parse through a series of strings with a given token list. I was wondering if my lexical analysis is correct. ...
152 views

• 367
1 vote
353 views

### Convert regex pattern to LL1 parser

Background: I'm trying to solve this leetcode problem: regular-expression-matching. My approach is to implement a LL(1) parser generator, might be overkilling for this problem but it's just a brain ...
• 113
1 vote
64 views

### Regular expression for all a* except aa?

I'm stumped on how you would describe a language which is a* except for aa, so the following is acceptable: a aaa aaaa aaaaa ... It's for part of the below DFA
1 vote
129 views

### I have found an example where regular expression is not closed under concatenation. Where am I wrong?

$a^n$ is a regular expression. $b^n$ is a regular expression. their concatenation is $a^nb^n$ which is not a regular expression.
1 vote