# Questions tagged [regular-expressions]

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

563 questions
Filter by
Sorted by
Tagged with
21 views

General Given a regular language $L \subset \Sigma^\star$, I wish to generate at least one string not in $L$. (Obviously, this requires that there exists such a string; i.e., that $L \neq \Sigma^\... 1answer 32 views ### What's the difference between phi and lambda in regular expression? I've been learning on Formal Languages and Automata of Peter Linz(6th edition). In the chapter 3 of this book, it explains the primitive regular expression. But I don't know what is the difference ... 1answer 166 views ### How hard is finding the shortest path in a graph matching a given regular language? Suppose we are given a directed graph$G = (V, E)$with edge weights$w : E \rightarrow \mathbb{R}$(we can assume there are no negative cycles) and edge labels$\ell : E \rightarrow \Sigma$from some ... 1answer 42 views ### How create DFA with multiple finished states for lexers? Is possible to create DFA directly from regular expression. But for lexical analyse is needed "joined" DFA with many finish states, for example one state for string, one for integers, one for floats ... 1answer 81 views ### Meta text processing concept I understand that text processing could be done in various ways on top of operating systems: Shell utilities for processing a file (and/or a file name): tr, ... 1answer 45 views ### Language to regex Let A={a,b}. So the question is to write regular expression such that L(r) which consists of all words. My answer is this: L(r)= (a+b)* a* b* (a+b)* Is this ... 2answers 116 views ### Uniqueness of solution in Arden's theorem Geeksforgeeks contains a proof of Arden's theorem, asserting that$R=QP^*$is the unique solution to$R=Q+RP$. The proof is reproduces below. My question is: What is the logical reasoning to prove ... 1answer 27 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 ... 1answer 104 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)^*$? 1answer 53 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. ... 0answers 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 ... 0answers 33 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 ... 2answers 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 ... 0answers 19 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? 1answer 61 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 ... 0answers 30 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 ... 1answer 46 views ### Different application of Arden's theorem leads to different answers So, I have to solve for the following set of equations$q_1$=$q_1$a +$q_2$b +$\epsilonq_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 ... 0answers 22 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 ... 0answers 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 ... 1answer 29 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 (.). ... 0answers 30 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 ... 2answers 67 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? 3answers 270 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 ... 3answers 884 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 ... 0answers 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 ... 3answers 143 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.... 1answer 39 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 ... 1answer 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 "... 1answer 28 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: ... 1answer 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 ... 0answers 28 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 ... 0answers 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 ... 1answer 49 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 ... 2answers 67 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 ... 1answer 59 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?:) 0answers 37 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 ... 1answer 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 ... 1answer 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, ... 1answer 74 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 - ... 1answer 43 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 ... 0answers 39 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 ... 1answer 397 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 ... 1answer 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 ... 2answers 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, ... 0answers 30 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 ... 0answers 97 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 ... 1answer 30 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 0answers 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 ...