Questions tagged [regular-expressions]

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

Filter by
Sorted by
Tagged with
0 votes
2 answers
29 views

Regex for string does not contain the substring "110"

Can anyone help me figure out the error in my approach to this problem from Sipser 1.18 (1.6f)? Write a regular expression for the language L = {w | w does not contain 110} So, the answer I get is: $(...
user avatar
0 votes
1 answer
29 views

Confused by Sipser's proof of equivalence of R and NFAs

I am reading Introduction To Theory of Computation by Sipser, 3rd Edition and am confused by his take on the last three cases of proving that "if a language is described by regular expression ...
user avatar
0 votes
1 answer
44 views

DFA and NFA with 2 Substrings

I am preparing for my CS exam and found this question in a collection of old exams: Find a DFA and NFA with Σ = {o,p,q} that checks if the substrings op and pq are present in the string. I thought, ...
user avatar
0 votes
1 answer
46 views

regex find substring matches in text

I have written a regex engine and it can match whole strings to a pattern without a problem, i.e.: match(E, w) and it returns ...
user avatar
  • 1
-2 votes
1 answer
45 views

Why is $L'=\{u\#v^R ~|~ u,v \in L\}$ and $L\in RL$ a regular language?

Define $L'=\{u\#v^R ~|~ u,v \in L\}$ and $L\in RL$ while $\#\notin \Sigma$ Why is $L'$ a regular language? I have tried to construct the DFA of L, then with a # move to a copy of this DFA with flipped ...
user avatar
  • 241
4 votes
1 answer
98 views

Are the set of all Bitcoin addresses a context-sensitive language?

This started with me trying to make a regex to accept Bitcoin addresses. However, I couldn't do it. That led me to think: "is the set of all possible Bitcoin addresses even a regular language&...
user avatar
-1 votes
2 answers
58 views

Regular Expressions with at least 3 b's and at most 2 a's

I am not a Regular Experssion expert, but my request is simple: I need to match any string that has at least 3 characters of B and at most 2 characters of A so for example: ...
user avatar
0 votes
1 answer
58 views

How would I design a State Diagram (FSM) for a AC unit?

Ok so I'm learning Finite Automata in my Theory of Computation course and understand the basic FSM but can't wrap my head around this question: The AC should only turn on if a person is detected in ...
user avatar
3 votes
2 answers
1k views

Length of a regular expression

What is the definition for the length of a regular expression? This question might sound simple, yet I cannot find a definition. Do I only count letters from the alphabet? Do * and $\cup$ count? For ...
user avatar
1 vote
2 answers
49 views

NFA to recognize the language ${ab}$

In Michael Sipser's Introduction to the Theory of Computation, Example 1.56 shows how to convert $\left(\text{ab }\cup\text{ a}\right)^*$ to an NFA. It builds up from the smallest subexpression to ...
user avatar
  • 113
1 vote
1 answer
78 views

Prove that the language of regular expressions is not regular

I want to prove that the language of all regular expressions is not a regular language. I'm having trouble to approach this problem. I thought maybe to show that the parenthesis language is a part of ...
user avatar
1 vote
1 answer
47 views

Why L1 := { a^n b^m | m, n ≥ 0 and m ≥ n } is regular and L2 := { a ^ n b ^ n | n>= 0 } not regular?

I understand why L2 is not a regular language. We can use the pumping lemma to prove it In the case of L2: assume n = 1 and string = ab We assume that L2 is regular, so it has "pumping length&...
user avatar
2 votes
4 answers
281 views

What exactly is pumping length in pumping lemma?

Pumping Lemma : For any regular language $\mathbb{L}$, there exists an integer $n$, such that for all $x\in \mathbb{L}$ with $|x|\geq n$, there exists $u, v, w \in \Sigma^*$, such that $x = uvw$, and ...
user avatar
-2 votes
1 answer
32 views

How to cross verify the resultant E-NFA in "Regular Expression to E-NFA" is correct?

Let's say that we want to convert the regular expression: (ab + a)* to Finite Automata, where '+' is union and '*' is kleene star. Using the Thompson method, Thompson Method I end up with this: My ...
user avatar
1 vote
1 answer
39 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, ...
user avatar
1 vote
1 answer
60 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 ...
user avatar
1 vote
2 answers
91 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 ...
user avatar
  • 11
13 votes
4 answers
2k 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. ...
user avatar
  • 233
0 votes
1 answer
66 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 ...
user avatar
  • 9
3 votes
1 answer
77 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...] ...
user avatar
1 vote
1 answer
36 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$, ...
user avatar
  • 13
1 vote
2 answers
166 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$, ...
user avatar
  • 155
1 vote
0 answers
44 views

Multithreaded Regex?

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 ...
user avatar
  • 123
0 votes
0 answers
21 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 <...
user avatar
1 vote
1 answer
60 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 ...
user avatar
1 vote
2 answers
24 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 ...
user avatar
0 votes
1 answer
45 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 ...
user avatar
0 votes
1 answer
96 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.
user avatar
0 votes
0 answers
34 views

Exercises on regular languages

I wanted to know if any of you have a regular language workbook or site. I would need to train on exercises like this: Y = {w ∈ {a, b} ∗ | w = a2 ^ i b ^2j + 1, i, j> 0} Y = {0 ^ n 1 ^ m | nm <6 ...
user avatar
  • 1
2 votes
2 answers
69 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)...
user avatar
1 vote
1 answer
421 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 ...
user avatar
1 vote
1 answer
67 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 ...
user avatar
  • 13
0 votes
2 answers
45 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
user avatar
  • 1
2 votes
0 answers
42 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 ...
user avatar
-2 votes
1 answer
98 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?
user avatar
  • 1
1 vote
1 answer
119 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 ...
user avatar
  • 111
1 vote
1 answer
155 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 ?
user avatar
0 votes
1 answer
48 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 ...
user avatar
0 votes
0 answers
42 views

Regex AST to NFA construction

I have written a parser for a regular expression using this grammar and it outputs an AST (abstract-syntax-tree). My goal is to create an equivalent DFA given the Regex AST which can be used to ...
user avatar
  • 129
0 votes
0 answers
7 views

CONVERTING NFA TO RE [duplicate]

How do I obtain the regular expression of this NFA? I have only done exercises where I obtain the RA from NFAs with only two states or when the third state is an accepting state and I simply follow ...
user avatar
-1 votes
2 answers
90 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 ...
user avatar
  • 1
0 votes
0 answers
19 views

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

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 ...
user avatar
-1 votes
1 answer
30 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. ...
user avatar
  • 1
4 votes
0 answers
135 views

Regular languages for which star height is not increased by complementation

The set of (non-generalized) regular expressions over an alphabet $\Sigma$ is the set of expressions generated by the following grammar, where $a\in \Sigma$ ranges over symbols in the alphabet: $$ \pi ...
user avatar
  • 41
1 vote
0 answers
10 views

Contiguous-substring operator

If string concatenation $ab$ is like left- and right-multiplication, is there any infix (latex) operator notation I can use for checking for contiguous substrings, like $bc \subseteq abcd$? $\subseteq$...
user avatar
  • 11
0 votes
0 answers
58 views

Decidability of the language of a regular expression being a subset of a given context free language

Let L be a language of pairs $\langle R,G\rangle$, with the first element being a regex and the second being a CFG. Is it decidable that G accepts whatever the regular expression does? In other words, ...
user avatar
2 votes
1 answer
102 views

Is regex with lookaround still regular?

It is well known that "regex" with back-reference is not a regular expression anymore. For instance, (.*)\1 matches any string repeated twice. However, is ...
user avatar
0 votes
1 answer
82 views

Simplifying regular expression

I'm having trouble understanding the simplification of the following regular expression \begin{align} R = ε | 1 | (ε | 1)(ε | 1)^*(ε | 1) = 1^* \end{align} In my lectures only the simplified solution ...
user avatar
10 votes
1 answer
594 views

What is the correct way to draw NFA of RE (a|b|c)?

We were assigned to draw NFA for regular expression a|b|c, so like any one I draw this But my professor told me it is wrong, the correct way is So, I checked it ...
user avatar
0 votes
0 answers
15 views

I cant figure out which regular experesion solves my problem [duplicate]

The language L=a binary number with even number of digits that doesnt have 2 consecutive zeroes. What is the regular expression that can search those words and how what is your thought process when ...
user avatar

1
2 3 4 5
16