Questions tagged [regular-expressions]
Questions about regular expressions, a formalism to describe regular languages.
563
questions
1
vote
1answer
21 views
Algorithm to generate inputs with certain properties, but not accepted by a given regular language
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^\...
1
vote
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 ...
5
votes
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 ...
0
votes
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 ...
1
vote
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, ...
0
votes
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 ...
-1
votes
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 ...
3
votes
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 ...
3
votes
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)^*$?
3
votes
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.
...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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?
4
votes
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 ...
1
vote
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 ...
1
vote
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 + $\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
...
0
votes
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 ...
1
vote
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 ...
0
votes
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 (.). ...
0
votes
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 ...
-2
votes
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?
3
votes
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 ...
5
votes
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 ...
0
votes
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 ...
3
votes
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....
4
votes
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 ...
0
votes
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 "...
0
votes
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:
...
3
votes
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 ...
0
votes
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 ...
0
votes
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 ...
2
votes
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 ...
4
votes
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 ...
0
votes
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?:)
0
votes
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 ...
3
votes
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 ...
-1
votes
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, ...
2
votes
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 - ...
2
votes
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 ...
0
votes
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 ...
2
votes
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 ...
1
vote
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 ...
0
votes
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, ...
2
votes
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 ...
5
votes
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 ...
0
votes
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
0
votes
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 ...
0
votes
1answer
46 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 ...
1
vote
1answer
133 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 ...
