# Questions tagged [regular-expressions]

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

635 questions
Filter by
Sorted by
Tagged with
152 views

### Are regular languages and their regular expressions part of computer science?

I am trying to understand if regular languages and their regular expressions are concepts of computer science in general and if these are discovered, or invented, by computer scientists, in particular....
45 views

### Is unification over regular expression equations doable?

By way of example, suppose I know that $X + a = b + Y$ where $X$ and $Y$ are variables standing for regular expressions, then $(X, Y) = (b, a)$ is a solution to this set of equations. Generalizing ...
19 views

### Regular Expressions to accept strings where every two successive 0s are followed by a 1

How do I define a Regular Expression for the language L = {w|every two successive 0s are followed by a 1} ? I don't have any idea on how to even approach this problem, primarily because it says "...
47 views

### Regular expression for containing 010 as a subword

I am studying for a test in computer science, and am encountering difficulties with regular expression. Here is example of a question I don't understand. I managed to solve the following question: ...
29 views

### Regular expressions with cycles

A knob is used to select one of three positions A, B, C. The knob can never be turned from A to C, or from C to A, without spending at least one second in position B. The initial position of the knob ...
49 views

### Proving that the language of regular expressions is not regular

Prove that the language consisting of all valid regular expressions is not regular. I am approaching this using the Myhill-Nerode Theorem as follows: I am trying to find a pairwise distinguishable ...
22 views

### Minimal DFA for “$n$th character from the right is $a$” [duplicate]

I am given the following regular expression, which accepts all strings over $\{a,b,c\}$ whose $n$th character from the right is $a$: $$(a|b|c)^*a(a|b|c)^{n-1}.$$ The exercise asks for the number ...
84 views

### Regular expression for language that does not accept x string (3 letters, |x|=3)

The language I am interested in is $L=\{w∈\{a,b,c\}^*| w$ contains "$bac$" but not "$cab$"$\}$. I am thinking that the result will have the form $L=X_1X_2X_3$, where $X_1=\{w∈\{a,b,c\}^*| w$ does not ...
219 views

### Finding the number of distinct strings in regular expression

Given the regular expression $(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )$, how many distinct strings are in the language? How do you determine this from ...
73 views

### The alphabet is {a, b}. Show that the set of words with the same number of occurrences of a and b is not regular [duplicate]

This is a question I've been asked to do and I honestly have no idea how to approach this. Help please?:)
219 views

### Regular expression for set of strings with no two consecutive 1's? [duplicate]

I'm having trouble figuring out a regular expression over the alphabet {0,1} that contains all strings with no TWO consecutive 1's. I'm also wondering if there is a pattern that could be extended to ...
132 views

### How do I solve these questions regarding homomorphism?

Questions: Give an example of a homomorphism, using the same alphabet, Σ, for both languages A and B. Now, give a second example of a homomorphism but this time using two different alphabets, Σ and ...
49 views

### Constructing a DFA of strings that are in A but not in B

I am tasked with creating a DFA for the regular language L = A/B, which are the strings that are in A but not in B. The alphabet is Σ = {a,b,c} I am not really sure where to even start with this one, ...
373 views

### Arithmetic operators and regex

Let $L$ be the language over the alphabet $\{0, 1, 2, 3, (,), +, -, *, /\}$, $L$ is the set of operations with correctly formatted natural numbers. A single number is considered to belong to $L$. 2 - ...
74 views

### Algorithm to Minimize a Regular Expression

I am referring to regular expressions with alphabet {$0$, $1$}. We want to minimize them so that they have the least possible number of symbols and operators. Is there an algorithm to do this? For ...
859 views

### show that if L is a regular, then drop(L) is a regular

I am trying to prove the following problem, but honestly I don't know what "proof" is considered a good proof. I tried to prove it by constructing an NFA that start with w1 and ends with wk, but I ...
29 views

### I need help in this regural expression exercises [closed]

Write a regular expression for the language of words over $\{0,1,2\}$ satisfying the following requirements: The word has length at least 3. The last symbol is 2. The second to last symbol ...
51 views

### No FSM/Regex exists for this language right?

The language is this: $L = \{w \in \{a,b\}*:$ each $a$ has a matching $b$ somewhere in $w$ $\}$ This wouldn't have an FSM since you'd need infinite states of depth for each unmatched a you have, ...
48 views

### Minimal regular expression from minimal NFA for finite language in polynomial time?

Given a minimal NFA for a finite language, is there a polynomial-time algorithm to find a minimal regular expression for the same language? This question is based on a recent question regarding ...
116 views

### Is there a polynomial-time algorithm to minimize regular expressions without Kleene closures/stars?

I have read that minimizing regular expressions is, in general, PSPACE-complete. Is it known whether minimizing regular expressions without the Kleene closure (star, asterisk) is in P? The language ...
55 views

### Lexicographic Order of Expression [Automata Theory]

what will be kleene star "expansion" of expression $a^*b^*$ in lexicographic order? I'm confused and I really want to clear my concepts so I can proceed further
28 views

### Uncommon case in Arden's lemma $q_{2} = 1q_{2} \cup 0q_{2}$

I'm trying to get the regular expression of an automata but an state has a form that I don't know how to solve, the form on its simplest example is: $$q_{2} = 1q_{2} \cup 0q_{2}$$ What's the ...
73 views

### Create automata from non regular grammar

I have two grammars: L → ε | aLcLc L → ε | aLcLc | LL This two grammars are equals but the first one is regular, so it produces a regular language and a ...
388 views

### Write down a DFA for the regular expression (000* + 111*)* and explain why it cannot have lesser number of states

So, I came up with a DFA for the regular expression. Now for every string described by the regular expression, the DFA accepts it. But in order to ascertain if it's really a DFA for the regex, you ...
2k views

### How do i tell if a grammar is regular or not?

I know that a regular grammar has a definition \begin{align}S &\to aS\\ S &\to \lambda \end{align} But I dont really know how to apply this information to check whether or not a grammar ...
53 views

164 views

### Regular Expression: Writing an expression with at least two characters in length? [closed]

A past exam question: (1) Consider the language, $L$, of strings over the alphabet $\{x, y\}$ of length at least 2 with the second symbol being $x$. For example, $yx$, $xxyy$, and $yxy$ are members ...
1k views

### Regex to match number ranges less than a certain number

I'm trying to write some code to match numbers below certain bounds. I would much appreciate nay help somebody could give, I'm pretty lost with this one... NB. I've checked the forums and can find ...
27 views

### Converting DFA to RE [duplicate]

I have been trying to solve this problem. Convert the DFA to a regular expression. I extracted these following equation. $q_1 = q_2a$ $q_2 = q_1a + (a+b)q_3$ $q_3 = q_1b + q_2a$ Also,the ...
116 views

### Kleene Star regex question, sed behavior? [closed]

Kleene Star with 'sed' is behaving as expected for me, with exception of a case where the input pattern is "ab" and the regex is "b*". Does anyone know why this regex is not being matched against the ...
56 views

### find derivation trees for CFG

I need to draw the derivation tree for $1-2-(3-4)*5*6$ from the grammar below. I want to know how many possible derivation trees are there from this grammar. \begin{align}V_n&=\{expr,term,...
89 views

### Why $P$ cannot have NULL string in Arden's Theorem?

Arden's Theorem says that in the equation $R=Q+RP$, the $P$ cannot have NULL string. In this respect,the theorem will not be valid for the expression $R=Q+R(NULL+01)$. Am I correct? If so, then what ...
383 views

### Converse of pumping lemma for regular expressions

I want to come up with a language that satisfies the pumping lemma while not being a regular expression. I thought of $\{0^i1^j: i > j > 0\}$. The pumping seems to work just fine, and this is ...
21 views

### regular expression with kleene closure [duplicate]

my question is if my regular expression R is 1* that means the language accepted is {^,1,11,111,1111...} in that case i don't understand the meaning what (R*)* means
63 views

### Counting number of states from a regular expression

Given the regular expression: $r=ab+((a+\epsilon)c^*)^*$. Let A be a non-deterministic automaton that accepts the language of r. How many states are in A? Answer the question without building A ...
30 views

### A deterministic FA for $0^*1^*$ is required

A deterministic finite automaton without $\epsilon$ steps for the language $0^*1^*$ is required. Any nice picture ? I have created a NFA for this language which has 2 states $Q_1,Q_2$, both are ...
63 views

### How generate regular expression on the alphabet {a,b}?

How can I write a regular expression that denotes language on the alphabet {a,b} of the strings that do not present "b" consecutive and the total number of "a" is multiple of three?.
12 views

### Regular expression notation clarification

For the alphabet $Σ$={a,b,c} I was wondering how you would say: T that has elements from Σ, so could be T=a, T=bc I was considering maybe $Σ^*$ or $Σ^+$ would describe that, but I am not sure ...
93 views

### Finding a regular expression of a language

Our alphabet is {a,b} and we need to find a regular expression for the language of all words of the form $a^*b^*$, whose length is a multiple of 3. Obviously $(aaa)^*(bbb)^*$ is one of the options, ...
89 views

### What is the best algorithm known to learn the regular expression from a set of positive examples?

I have a blackbox program that generates a set of strings. What is the best regular expression learner that I can use to learn (approximate) what the blackbox program uses as a generator? Note that I ...
67 views

### Regex NFA construction: Why use Glushkov over Thompson? Pros/Cons

In what circumstances should we prefer Glushkov's algorithm or Thompson's construction for the building of regular expression NFAs? I understand the difference between them, and can follow the ...
544 views

### DFA multiple accepting states to Regular expression

I am trying to find the regular expression that defines this DFA, I am finding this particular case difficult since it has multiple accepting states. If I understand this DFA correctly, it recognises:...
128 views

### Regular Expression For The Language Σ = {0,1}

I have an language of Σ = {0,1} and need to find the the regular expression of: Set of strings that have no pairs of consecutive zeros Set of strings that contain ...
74 views

### Is there an algorithm to overapproximate a context free grammar by a regular expression?

I understand that a context-free grammar is strictly powerful than a regular expression in that a context free grammar can represent any regular language, but not all context free languages can be ...
46 views

### Transform Double Metaphone code into regex

I am using hyperscan to search through large texts for a lot of regexes. One addition should be selective phonetic search for individual words. The algorithm of choice is Double Metaphone (but please ...
1k views

### Regular Expression: L= {w | every even position of w is '1'}

I am trying to solve a regular expression of binary string where every even position is a '1' I've solved this for an odd position: (1(0+1))*(1+ε) How would it look like for an even position then? ...
146 views

### Define a finite automaton accepting the language below [duplicate]

$\{ w∈(a,b)^\ast | w$ does not contain '$ab$' as a subword $\}$. About questions like this, I always want to construct the regular expression for it, then convert the regular expression to a finite ...
32 views

### Modelling regex replacement via a DFA

I wish to model the following common construction in code via a finite state automaton for the purposes of static analysis: ...