# Questions tagged [regular-expressions]

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

560 questions
Filter by
Sorted by
Tagged with
27 views

### What is the logical reasoning behind Arden's Theorem proof of unique solution?

Here is the proof for Arden's Theorem assertion that R=QP* is the unique (only solution) to R=Q+RP. My question is: what is the logical reasoning to prove that any equation is the unique (only ...
21 views

### Converting DFA to RE with Arden's Rule

So I've searched around and found the algorithm to do so: How to convert finite automata to regular expressions? and I decided to test out the second-level response, Raphaels, and while I was getting ...
101 views

### Regular expression for strings not starting with 10

How can I construct a regular expression for the language over $\{0,1\}$ which is the complement of the language represented by the regular expression $10(0+1)^*$?
24 views

### Show that this language L' is regular [duplicate]

I'm not even sure where to begin with this. The language given is: L' = { x∈Σ* | ∃y∈Σ*, |x|=|y| and xy ∈ L}. Basically, L' consists of the first halves of the strings in L, where L is a regular ...
50 views

### Prove the equivalence of regular expressions

I have a question relating to regular expressions that I'm a bit confused about, If someone can help me out, that would be very much appreciated. Suppose there exists regular expressions R, S and T. ...
13 views

### Regular Expression for a^nb^m such that n<= m+3 [duplicate]

I want to know if its possible to write a regular expression for a context free language: For example I have a language : L={a^n b ^m: n<= m +3} I have written the following regular expression ...
21 views

### Regex Questions?

I need to match all words having two adjacent vowels that differ. I did this /\b(?=\w*([aeiou])(?!\1)[aeiou])\w+/ but I am not allowed to use the ?! and it needs to be done in as few characters as ...
12 views

### Regular expression containing lambda

What is the meaning of lambda here: $$(b+c)^*(a+\lambda)(b+c)^*(a+\lambda)(b+c)^*(a+\lambda)(b+c)^*$$. I know that lambda is used in the context of NFA? Let's suppose we break down the expression ...
18 views

### Is this language regular or not regular {(a* union b)a } intersection {a*b*} is a regular language [duplicate]

Is {(a* ∪ b)b } intersection {a* b* } a regular language?
58 views

### Can every regular expression be written as sum of products?

I was trying to prove that Parikh Image of every regular language is semi-linear. Even though it is true for CFL, but this question was about regular languages. To prove this, I decided to proceed as ...
26 views

### Is ASM a regular language?

I'm giving a presentation where I have a single slide dedicated to formal languages. In this slide I give a simplified overview of the Chomsky Hierarchy and I'd like to give an example of a real world ...
16 views

### Regular expression required [duplicate]

Give a regular expression for L={a^n b^m |n>=1,m>=1,nm>=3} I tried something like this: a(a)* . bbb(b)*
46 views

So, I have to solve for the following set of equations $q_1$ = $q_1$a + $q_2$b + $\epsilon$ $q_2$ = $q_1$a + $q_2$b + $q_3$a $q_3$ = $q_2$a There are two ways to do this. I did this ...
21 views

### What exactly is “pattern matching”?

I know some examples of "pattern matching". E.g. in the context of functional programming, and regular expressions. But is there a precise definition? In particular, it seems that it has to do with ...
34 views

### Regular expressions for set of all strings on alphabet $\{a, b\}$

I came across following regular expressions which equals $(a+b)^*$ (set of all strings on alphabet $\{a, b\}$): $(a^*+bb^*)^*$ $(a^*b+b^*a)^*$ $(a^*bb^*+b^*ab^*)^*(a^*b+b^*a)^*b^*a^*$ I want to ...
25 views

### Regular expression and Right Regular grammar for decimals starting with 1 ending with 9?

I was trying to do the following: Consider the set of all strings over the alphabet {0,1,2,9} that are decimal numbers beginning with 1 and ending with 9 and having exactly one decimal point (.). ...
27 views

### What is a Regular BNF Grammar and a Regular Expression for (simple) Resource Identifiers?

I was trying to make a regular grammar for resource identifier described as follows: Consider the set of all strings over the alphabet $\{ a, b, / , . \}$ that represent an RI (resource ...
62 views

### $L_1 ∩ L_2$ is not regular while $L_1$ is regular and $L_2$ is not regular language

Could you give me an example of languages $L_1$ (regular) and $L_2$ (not regular) where $L_1 \cap L_2$ is not regular?
252 views

### Regular Expression with at least one a, even number of b

I've been working on some regular expression questions, and came across one that I cannot figure out. Working on the language over $\{a, b\}$, the text asks for a regular expression for the language ...
880 views

### How to determine minimum word length of regular language

Given a regular language $L$ and a regular expression $r$ with $L=L(r)$. Is it possible to determine the minimum length of words of $L(r)$ by the structure of $r$? A straightforward example: Let's ...
8 views

### Binary string regex problem, starts with a 1 and has an even number of 0s [duplicate]

I am trying to make a regex expression that is: A binary string that starts with a 1, and has an even number of 0s. I tried, 1(1*01*01*)*, but it misses the case where it is 11. How would I go about ...
122 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....
37 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 "...
27 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 ...
16 views

### Help in converting NFA to regular expression [duplicate]

Hi I don't understand how to convert NFA to regular expression in the question below. Can someone help me to solve and understand example below
26 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 ...
48 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 ...
60 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 ...
57 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?:)
35 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 ...
116 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 ...
46 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, ...
53 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 - ...
39 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 ...
36 views

### How to prove that L(G) is not regular by contradicting the pumping lemma?

I am trying to prove that this language is not regular by contradicting the pumping lemma. I have been reading and looking at examples but all the examples I have seen is in the for of a REGEX. I am ...
316 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 ...
25 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 ...
47 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, ...
29 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 ...
95 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 ...
26 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
26 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 ...
43 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 ...
115 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 ...
366 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 ...
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 ...