Questions tagged [regular-expressions]
Questions about regular expressions, a formalism to describe regular languages.
547
questions
1
vote
0answers
23 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
19 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
25 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 ...
-1
votes
2answers
58 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
238 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
862 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
116 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
35 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
18 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
26 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
28 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 ...
-1
votes
0answers
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
0
votes
0answers
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 ...
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
42 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
59 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
55 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
34 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
112 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
44 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 - ...
1
vote
1answer
35 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
35 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
287 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
23 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
46 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
26 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 ...
4
votes
0answers
92 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
20 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
41 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
107 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 ...
1
vote
2answers
245 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 ...
0
votes
1answer
27 views
Need help understanding regular expressions
I was reading up about formal languages (see here: https://pdfs.semanticscholar.org/18b2/d685d5e244a6bfc5a31d312f1e8d322c16a9.pdf) and got confused when I started reading about this expression: 0(0+1)∗...
-2
votes
1answer
41 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 ...
0
votes
0answers
126 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 ...
0
votes
0answers
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 ...
1
vote
1answer
43 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 ...
0
votes
1answer
43 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,...
2
votes
1answer
30 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 ...
3
votes
2answers
230 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 ...
0
votes
0answers
19 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
0
votes
1answer
26 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 ...
1
vote
1answer
26 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 ...
0
votes
0answers
52 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?.
2
votes
1answer
10 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 ...
2
votes
1answer
91 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, ...
0
votes
0answers
43 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 ...
2
votes
0answers
26 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 ...
