# Questions tagged [regular-expressions]

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

518 questions
Filter by
Sorted by
Tagged with
76 views

### How to read regular expressions? [closed]

Consider the following regular expressions ...
563 views

### Regular Expression for {W | W contains an even number of As and an odd number of Bs, but doesn't contains AB}

While studying Automata at my University, I faced the following problem from SIPSER, M textbook: Consider D = { w | w contains an even number of as and an odd number of bs and doesn't contains the ...
66 views

### What does $k$ mean in regular expressions?

From what I have learned in Introduction to Automata Theory, Languages, and Computation, regular expressions can be represented with $R^{(k)}_{ij}$. I understand that $i$ and $j$ represent the ...
52 views

### Regular Expression Metric space

With Levenshtein distance we can create a metric space over string. Is there are any distance metrics for regular expressions?
2k views

### How to convert DFA to regular expression using arden's rule

I generally use state removal method to convert DFA to regular expressions. But I want to try other methods like using algebraic methods and arden's rule. How to solve a DFA with multiple final ...
17 views

209 views

### How to disambiguate symbolic regular expressions

What I mean by a "symbolic regular expression" (if there already is a different name for this I'm not aware of it) is a regular expression that may include exponents that are symbolic arithmetic ...
218 views

### Prove that $L=\{a^i b^j c^k \mid i=1$ implies $j=k\}$ is NOT regular [duplicate]

Are there any closure properties which I can use to come up with a contradiction?
103 views

### Prove that the language { uw : |u| =2 |w| } is regular

I have a problem with this following question: Prove that the language $\{uw : |u|=2|w|\}$ is regular. I tried to give this regular expression $(uw²)^*$ to resolve it.
349 views

### Minimal regular expression that matches a given set of words

I have a dictionary-like regular expression, an "or chain" of words, word1|word2|word3|... Unfortunately, the chain is too large. I'd like to find the minimal ...
112 views

### Creating a Grammar that is equivalent to “RegEx A, RegEx B, or BOTH”

I have the following problem, create a Grammar on the Language {1,0} that accepts "strings with a length divisible by 3, or strings with a number of 0s divisible by 3, or BOTH". I created ...
855 views

### Converting REGEX to BNF grammar

Say I have a bunch of regex expressions which are used as filtering rules. (Any special extraction capabilities are unnecessary here, the set of regular expressions I have is only used for filtering ...
118 views

### Regular expressions for words avoiding aaa,bbb,ccc [duplicate]

I need to write a regular expression for all words over $\{a,b,c\}$ not containing $aaa$, $bbb$ or $ccc$. Will appreciate any help. Note: this is not homework.
677 views

### Drawing a DFA for a language/regular expression

how would you draw a DFA for the language over {a,b,c} of all words where every occurrence of b is preceded and followed by a. My thinking of this is that the regular expression for this is a* c* (...
42 views

### Verification of regular expression computed from finite automata

Here in the given image, our question is to find regular expression from finite automata. I found three answers based on which state I am resolving. Are these answers in the photo correct? If any ...
144 views

### Regexp substitution and finite-state transducers

Many programming languages support a "regular expression substitution" operation: if r is a regular expression and s, ...
37 views

### Can a regular expression based “grammatic” be programatically minimized?

I have a list of pairs like (regex, substitute) that take quite long to apply to some input text so I was thinking about optimizing them a bit. From my knowledge for each regular expression there is ...
150 views

119 views

### Regular Expression for All strings which contain no runs of a's of length greater than two.On L={a,b,c} [closed]

My attempt is We can fairly easily build an expression containing no a, one a, or one aa: (b+c)(€+a+aa)(b+c) but if we want to repeat this, we need to be sure to have at least one non-a between ...
2k views

### Why isn't it simple to count the number of words in a regular language?

Given a DFA, A, let L(A) denote the number of words A accepts. I think it's easy to calculate L(A): Translate the encoding of A into a regular expression. If the Kleene star appears anywhere in the ...
I'm trying to find a regular expression for the following language: $$L=\{x0y : \text{x contains same number of 0's as y contains 1's}\}.$$