Questions tagged [regular-expressions]

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

Filter by
Sorted by
Tagged with
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
39 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
70 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
34 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
241 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
28 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
24 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
42 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
1 answer
56 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
55 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
74 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
34 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
1 answer
58 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
  • 111
1 vote
0 answers
28 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
19 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
56 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
23 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
40 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
81 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
33 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
2 votes
2 answers
64 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
394 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
56 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
40 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
  • 15
2 votes
0 answers
36 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
92 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
  • 15
1 vote
1 answer
81 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
149 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
44 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
33 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
0 votes
1 answer
54 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
0 votes
1 answer
24 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
29 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
1 vote
0 answers
61 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
70 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
556 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
2 votes
1 answer
52 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 ...
user avatar
  • 19
0 votes
1 answer
43 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 &...
user avatar
  • 1
0 votes
1 answer
32 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 ...
user avatar
  • 101
0 votes
1 answer
27 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 ...
user avatar
0 votes
1 answer
51 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 ...
user avatar
  • 9
3 votes
2 answers
773 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.
user avatar
  • 31
0 votes
0 answers
42 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 ...
user avatar
1 vote
1 answer
52 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$...
user avatar
  • 11

1
2 3 4 5
16