Skip to main content

Questions tagged [regular-expressions]

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

Filter by
Sorted by
Tagged with
1 vote
1 answer
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, ...
Pratik Hadawale's user avatar
1 vote
1 answer
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 ...
Pratik Hadawale's user avatar
1 vote
2 answers
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 ...
aye.son's user avatar
  • 11
13 votes
5 answers
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. ...
Keio203's user avatar
  • 257
0 votes
1 answer
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 ...
Minhaz's user avatar
  • 9
3 votes
1 answer
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...] ...
eternalstudent's user avatar
1 vote
1 answer
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$, ...
bafgil's user avatar
  • 13
2 votes
3 answers
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$, ...
john doe's user avatar
  • 177
1 vote
0 answers
126 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 ...
Sam's user avatar
  • 133
0 votes
0 answers
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 <...
Tommasosp13's user avatar
1 vote
1 answer
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 ...
SVMteamsTool's user avatar
1 vote
2 answers
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 ...
CforLinux 's user avatar
0 votes
1 answer
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 ...
SVMteamsTool's user avatar
0 votes
1 answer
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.
LetsGoBrandon's user avatar
2 votes
2 answers
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)...
Lucas Timothy's user avatar
1 vote
1 answer
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 ...
AutomotaNoob's user avatar
1 vote
1 answer
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 ...
yaman's user avatar
  • 13
0 votes
2 answers
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
Bubino's user avatar
  • 111
2 votes
0 answers
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 ...
user2373145's user avatar
-2 votes
1 answer
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?
Bubino's user avatar
  • 111
1 vote
1 answer
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 ...
A. Bond's user avatar
  • 111
1 vote
1 answer
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 ?
Ash Rivers's user avatar
0 votes
1 answer
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 ...
onesaffron's user avatar
-1 votes
2 answers
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 ...
george's user avatar
  • 1
0 votes
0 answers
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 ...
sofiatb's user avatar
-1 votes
1 answer
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. ...
zzzzz's user avatar
  • 1
4 votes
0 answers
152 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 ...
Tom's user avatar
  • 41
1 vote
0 answers
19 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$...
andi's user avatar
  • 11
0 votes
0 answers
164 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, ...
ali rezaei's user avatar
4 votes
1 answer
272 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 ...
user12986714's user avatar
0 votes
1 answer
408 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 ...
Simulacrum's user avatar
10 votes
1 answer
1k 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 ...
Harshil Modi's user avatar
2 votes
1 answer
157 views

Convert a dfa to rule for a asterisk case

Here is a simple but very common grammar rule case in EBNF format, the Statements is a none terminal symbol and Statement is ...
Swordow's user avatar
  • 19
0 votes
1 answer
523 views

Can any language be expressed by regular expression?

I'm studying Autoamta Theory currently and am wondering if any Language (for example Lanugage L in Alphabet A={a,b}) can be expressed by regular expression. In my current understanding the rule is &...
Ferris's user avatar
  • 1
1 vote
2 answers
169 views

Empty string in an ambiguous grammar?

I'm a bit confused by the role of the empty string in this ambiguous grammar: A' -> A A -> if A B A -> null B -> [empty string] B -> else S So what ...
Shisui's user avatar
  • 121
0 votes
1 answer
363 views

Can a non-regular language have a regular grammar?

Basically the title. I am supposed to find a regular grammar for the language that produces palindromes. This is all I have right now: S -> 1 | 0 | ε Since it ...
xyzNetdot's user avatar
0 votes
1 answer
3k views

Regular expression for set of all strings containing no 3 consecutive 0s?

The answer is $1^*01^*01^*+1^*(0+00+\in)1^*$ If I had to rephrase my question, it would be how to approach regular expression problems? Is it all about practice? How do I understand what the regular ...
custep's user avatar
  • 7
3 votes
2 answers
2k views

Regular Expressions - What is difference between a+ and a⁺

I'm very confused as to if a+ and a⁺ mean the same thing or are completely different.
Giles's user avatar
  • 31
0 votes
0 answers
68 views

conversion of regular expression to automata

I've a task to specify a finite automata (of any kind) that accepts the language described by this regular expression: $a(bab)^+b^*|(ab)^*(aa)^+$ My first solution looks like this: I would like to ...
crystalsky's user avatar
1 vote
1 answer
247 views

Regular expression for words without two equal consecutive letters

I need to find a regular expression for the language over $\{a,b,c\}$ consisting of all words in which no two consecutive letters are the same. For example, $abacbabca$ is in the language, while $abbc$...
Daniel's user avatar
  • 11
2 votes
1 answer
422 views

Are Nondeterministic Finite Automata not allowed 'sink-states'?

By definition are Nondeterministic Finite Automata not allowed a 'sink-state' (non-accepting state we don't get out of)? I can see us having them for NFA but not necessary but do not see how they are ...
rocktarmadeyah's user avatar
2 votes
1 answer
450 views

How to interpret the regular expression 0*10|01(01)*?

I'm having some trouble understanding the regular expression $0^*10|01(01)^*$. The expression matches strings like $00010$. But for some reason, I wasn't able to find a string that matches the $(01)^*$...
Kiruphasankaran Nataraj's user avatar
1 vote
1 answer
163 views

set theory with RegEx on fen strings (or another parser)

how can you find if a regex call is a subset of another regex call on an predictable set of data I have a string (chess Forsyth–Edwards Notation (FEN) string...
cubesareneat's user avatar
2 votes
2 answers
68 views

If L is regular so is the language of compressed doubles

Suppose L is a regular language over the alphabet $\Sigma$. I need to prove that $$ L'=\{x_0\cdots x_n:x_0x_0x_1x_1\cdots x_nx_n\in L, \ \ x_i\in \Sigma\}$$ I thought I could take a DFA which computes ...
Addem's user avatar
  • 367
1 vote
1 answer
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 ...
hackape's user avatar
  • 113
1 vote
1 answer
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
Fraser Langton's user avatar
1 vote
1 answer
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.
Aditya Kumar's user avatar
1 vote
1 answer
1k views

How to write a regex for repeated patterns

I have an alphabet $\Sigma = \{a,b,\#\}$. I'm trying to write a regex that only accepts strings that have the same pattern before and after the $\#$ without using back references. For example, $aab\#...
Nakul Upadhya's user avatar
1 vote
1 answer
729 views

What is the regular expression for the language, {w | w does not contain the substring 11}

{w | w does not contain the substring 11} What I am thinking: $(0^* 1 0^* )^*$ Is anything wrong with my expression? Thanks in advance for your help!
Geoffery Quansah.'s user avatar
0 votes
1 answer
117 views

Simplifying the Language of this DFA

Above's the DFA in question (Sipser, Page 36). I have obtained the language of this DFA to be 0*1(1+00+01)*. But Sipser's textbook goes on to explain that the language of this DFA is (0+1)*1(00)*. But ...
PDK's user avatar
  • 46

1 2
3
4 5
17