Questions tagged [regular-expressions]
Questions about regular expressions, a formalism to describe regular languages.
1
vote
1answer
167 views
Are regular expressions a*a and aa* equivalent?
Let $\Sigma = \{a, b\}$ an alphabet. Are the regular expressions $a^*a$ and $aa^*$ over $\Sigma$ equivalent? Even though concatenation is not commutative, in this case it seems like the statement is ...
-1
votes
0answers
14 views
Please give the answer of a regular expression for a string whose length is exactly two. a& b are the two symbols [on hold]
Question based on regular expression
Regular expression for a string whose length is exactly two.
a and b are the two symbols
0
votes
0answers
37 views
construct regular expression for a language [duplicate]
I want a regular expression for the following language.
(a+b+c)*, but does not contain substring "abab".
That means it can be any combination of (a, b, c) except "abab".
I tryed to construct it ...
1
vote
2answers
36 views
DFA & RE from descriptive definition of given regular language
I am trying to make the DFA and RE of a regular language which is define on the alphabet = {1,0} and all the strings present in these languages have exactly one 010 substring in them.
Some strings ...
2
votes
2answers
61 views
DFA of (aa+bb)(a+b)* + (a+b)*(aa+bb)?
Our class teacher gave us a descriptive definition of a language in a Quiz today and ask us to make its DFA. In the middle of quiz he also told us the Regular Expression(RE) of that language but we ...
0
votes
0answers
32 views
Returning all the combinations of a string using regex
Is it possible for a regex pattern to return all the 2^n combinations of characters of a string as matches?
For example, if the string is ...
4
votes
2answers
53 views
Does there exist a context-free language $L$ such that $L\cap L^2$ is not context-free?
I can see that $L$ has to be context-free but not regular here as regular languages are closed under concatenation and intersection. But $L\cap L^2$ looks too weird. I couldn't think of any $L$ that ...
3
votes
2answers
54 views
Regular expression for binary words with 1 in the middle
Given the alphabet $\{0,1\}$, generate a regular expression with the following language: $$ \{w\in \Sigma^* \mid w \text{ has odd length and its middle symbol is }1\}. $$
I'm having trouble finding a ...
0
votes
1answer
27 views
$ L = \{xyyz\in\{0,1,2\}^{*} : y \neq \epsilon \wedge \exists_{a \in \{0,1,2\}} |y|_a \equiv 0 \}$
$ L = \{xyyz\in\{0,1,2\}^{*} : y \neq \epsilon \wedge \exists_{a \in \{0,1,2\}} |y|_a \equiv 0 \}$
I think this languages is regular. I write regular expression:
$(1 + 2 + 0) ^ {*} (11 + ...
1
vote
2answers
75 views
Is the language of words that contain a square regular or context-free? [duplicate]
$ L = \{w \in\{a,b\}^{*} : \exists_{x,y,z} , w=xyyz \wedge y \neq \epsilon \}$
I have a problem with this exercise. I need to determine if this language is regular, context-free or not both and ...
1
vote
1answer
59 views
State-elimination on FSA, after epsilon-removal construction
I want to define the language of this FSA with a regular expression. I have learned that by state-elimination, I would be able to find a regular expression.
But there are already some epsilon ...
2
votes
1answer
37 views
How to use homomophism in closure proofs?
I am having a hard time understanding homomorphism. All I seem to understand is that it is a substitution. When I look at examples of proving closure of a particular operation over a regular language, ...
0
votes
1answer
36 views
Maximum number of words in deterministic finished automata with k-states [closed]
I have exercise:
We have a given finished deterministic automata. It has 5 states and is
based on the alphabet {a, b, c}. It can create n different words (we assume that n <
inf). What maximum ...
1
vote
1answer
36 views
Difference between methods of converting from finite state machine to regular expression
I have a question about method that I saw on internet and method that my professor showed me. I have this finite state machine:
...
0
votes
1answer
22 views
Product of Lexical Specification
I have a problem that asks me to consider the string abbbaacc. I'm supposed to figure out which of the following lexical specification produces the tokenization ab/bb/a/acc.
The options are:
...
1
vote
1answer
39 views
Why is this not recognized by a DFA?
I am still confused over my professor's explanation on why this problem is not a DFA.
The Problem: Explain why $L = \{p^kq^k \mid k>0\}$ cannot be recognized by a DFA
My professor explained it as ...
1
vote
1answer
35 views
How to prove that $\{\$x\$\}$ is a regular language if $x$ is derived from $L=\{w\}$ by substituting substrings?
Prove that if $L$ is regular over $\Sigma=\{0,1,2\}$ then the following language over $\{0,1,2,\$\}$ is also regular:
$$
G=\{\$x\$|\exists w\in L: x\text{ is derived from }w\text{ by substituting } ...
1
vote
1answer
37 views
Is this context-free grammar correct for this regular expression?
I have created a context-free grammar
$$
\begin{align*}
&S \to S_1 \mid S_2 \\
&S_1 \to aS_3bS_4 \mid \epsilon \\
&S_2 \to bS_4 \\
&S_3 \to aS_3 \mid \epsilon \\
&S_4 \to aS_4 \...
0
votes
0answers
14 views
What are some differences between regex (FSM) in computer science with regex in programming? [duplicate]
Computer science has automata theory with lessons on regular expressions and FSM. How are these different from regex engines used in programming such as C++, Perl, PHP etc.?
I would like to know some ...
-3
votes
2answers
75 views
DFA accept 00 as a substring
How can design this question if we have an equation like that
={wxw | w={0,1}* , x=00} accept 00 it means not contain 000,001,100, but accept all these {00,1001,110011,001000001.....}. Thank you for ...
0
votes
1answer
80 views
Regular expression or automata for language with odd number of 0's and odd number of 1's
Let $\Sigma=\{0,1\}$ and $L=\{u \in \Sigma^* : u \text{ has odd number of 0's and odd number of 1's}\}$. How can I build a regular expression or an automaton for this language? I have no idea, and I ...
0
votes
0answers
27 views
How use generalized suffix tree to match prefix string?
I know that generalized suffix tree can match substring for a given pattern.
But I have need a data structure which is able to
match prefix of many strings.
match sub string of of many strings.
For ...
1
vote
2answers
37 views
Does this DFA describe this regular expression?
For the expression (ab)*ba I came up with the following (very poorly drawn):
However, this was not the correct answer - apparently the solution requires five ...
0
votes
0answers
20 views
Formal Class of Languages Describable by .NET Regular Expressions
This is sort of a computer science question and sort of a programming question. What is the name of the formal class of languages that can be described by .NET regular expressions (assuming it a well ...
1
vote
1answer
42 views
Regular expression over alphabet A = {0 , 1, 2} for words that contain at least one 0 and don't contain 11
I got that I can get (1) followed by not (1) like this
$$ (0+2)^*1(0+2)^* $$
From this point I'm actually stuck. I can't set the (0) to be somewhere in expression. The only expressions I get are ...
3
votes
1answer
39 views
Regular expression for words containing single 1 and even number of 0s
What would be a regular expression for the language of words containing a single 1 and an even number of 0s?
0
votes
1answer
61 views
In RegExr, why is regex OR in JavaScript sometimes not commutative?
On https://regexr.com/, using the default JavaScript (Browser) engine, the languages $L(a^*|b^*)$ and $L(b^*|a^*)$ are not the same.
The first one matches only $a$'s and the second one $b$'s.
Is ...
1
vote
3answers
202 views
Regex for bit strings with at least two zeros but no consecutive zeros
This is what I have:
$$(1^*011^*011^*)^*\,.$$
But I don't think this is accounting for an odd number of zeros, like "$10101010101111$". I think I have the right expression that satisfies no 2 ...
2
votes
1answer
36 views
Subset of a regular language, for each of whose words there exists an element with the same number of 1s in the other regular language
For regular languages $A,B\subseteq\{0,1\}^*$, is
$$L_2 = \{x \in A \mid \exists y \in B : |x|_1 =|y|_1 \}$$
regular, where $|x|_1$ means the number of appearances of 1 in the word $x$?
i need to ...
0
votes
1answer
91 views
Is this concatenation of two FA done right?
$r_3=r_1r_2=(a^*b)^*(a+ba)^*bb(a+b)^*$ comes out to be $r_3=r_2=(a+ba)^*bb(a+b)^*$ when i generate the resultant FA and its regex after concatenation i.e. it doesn't include $r_1$
Details:
Consider ...
2
votes
2answers
433 views
Language of all strings that has exactly 1 triple b
I am new to automata and learning to make regular expression for languages. But I have been stuck on this one.
Suppose we have a language L, Language of all strings that has exactly 1 triple “b” ...
1
vote
1answer
37 views
Determining initial and final states from FA diagram
I am new to automata. And learning to find concatenation of two FAs. But this one has confused me
I know how to do concatenation but I am confused that in FA 1, what does x1 means? Is it mean final ...
0
votes
1answer
50 views
regex - difference between $\Lambda+(a+b)^*b$ and $(b+aa^*b)^*$
$r_1=\Lambda+(a+b)^*b$
$r_2=(b+aa^*b)^*$
$r_3=b+\$+aa^*b+(b+\$+aa^*b)(b+aa^*b)^*(b+\$+aa^*b)$
For this FA, which i think of as accepting "$\Lambda$ or anything ending in $b$", i came up with $r_1$, ...
0
votes
1answer
34 views
Can someone explain the language L = {w: w = uu, u \in La(1*01*)}
I need help understanding the language L above.
These are my understanding:
- w = uu is a concatenation of ...
1
vote
0answers
30 views
Extending Thompson's NFA algorithm with backreferences
I'm looking for an algorithm as efficient as possible for a regex engine that supports submatch tracking (a.k.a capturing parentheses) and backreferences. What I mean by as efficient as possible is ...
1
vote
1answer
44 views
Finding a correct regex for the strings with at least two $0s$
I am learning CFGs and before that I've made a RE (Regular Expression) for the language of "all strings with at least two $0$'s over the alphabet $\Sigma = \{0,1\}$."
I made this: $(0+1)^*0(0+1)^*0(0+...
1
vote
1answer
27 views
In which environment we use NFA(Non Deterministic Finite Automata)?
We have two types of Automata. One is NFA and second is DFA. These are little bit different but thing is that in which environment we prefer NFA over the DFA?
2
votes
1answer
67 views
Why does the concatenation operation imply the empty string?
I'm a noob reading Michael Sipser's Introduction to the Theory of Computation, and I'm at a part where he's demonstrating how to construct finite automata that accept languages described by regular ...
0
votes
0answers
19 views
Example of a language with linear NFA, but exponential DFA [duplicate]
So I read that regex engines use NFAs instead of DFA because f size blowup for dfas. I want to get an example of a language for which the minimum DFA has an exponential number of states but it,s NFA ...
10
votes
3answers
2k views
Why is there no permutation in Regexes? (Even if regular languages seem to be able to do this)
The Problem
There is no easy way to get a permutation with a regex.
Permutation: Getting a word $$w=x_1…x_n$$ ("aabc") to another order, without changing number or kind of letters.
Regex: Regular ...
1
vote
0answers
60 views
How to design a LL(1) grammar for basic regular expression?
I try to design a LL(1) grammar to parse the basic regular expression. Here's the origin grammar.（\| is the escape character, since | is a special character in grammar's pattern).
...
1
vote
1answer
43 views
Proving that L is not regular by showing that $\equiv_L$ has infinite index
Proving that L is not regular by showing that $\equiv_L$ has infinite index.
$\Sigma$ = {a}, L = {$a^{3^n} : n \geq$ 0}
My ideas:
theorem of Myhill-Nerode: L $\in$REG $\Leftrightarrow$ $\equiv_L$ has ...
0
votes
1answer
36 views
$L_n = \{x \in \Sigma^{*} | \exists w, y, z \in \Sigma^*, x = ywz, w^r = w, |w| = n \}$ Informally x is palindrome of length n. Find regex for n = 1
$L_n = \{x \in \Sigma^{*} | \exists w, y, z \in \Sigma^*, x = ywz, w^R = w, |w| = n \}$
Informally x is palindrome of length n
where $\Sigma = \{0,1\}$
I'm having a hard time understanding this ...
1
vote
2answers
55 views
Prove or disprove L is regular
There is question in one of my exercise but I couldn't prove or disprove anything about it.
This is language $L$ which is introduced with grammar:
$$S \to 0S1 | 1S0 | AA$$
$$A \to 0A | \lambda|A1$$
...
1
vote
1answer
53 views
Regular expression for $\{x : \#_{01}(x) \mod 3 = 0\}$
Let $L_1$ be the language over alphabet $\{0, 1\}$ defined by $L_1 = \{x : \#_{01}(x) \mod 3 = 0\}$.
Give a regular expression that denotes $L_1$, and justify its correctness
Attempt
Believe this ...
-1
votes
1answer
17 views
Show that $R^{+} \equiv R \leftrightarrow L(RR) \subset L(R)$
Show that $R^{+} \equiv R \leftrightarrow L(RR) \subset L(R)$
sigma is any alphabet. R is a regular expression.
How can L(RR) even be a subset or equal to L(R)?
1
vote
0answers
60 views
What is the regular expression for the following language?
What is the regular expression for the following language?
$$L = \{acbc: a,b,c \in \{0,1\}^+ \}$$
maybe we can say $$L = ((0 + 1)^+ 0 (0 + 1)^+ 0) + ((0 + 1)^+ 1 (0 + 1)^+ 1)$$
Is it true??
1
vote
2answers
52 views
Regular expression for words where the same symbol can repeat at most two times consecutively?
Having the alphabet $\{a, b\}$, how can I generate a regular expression for the language that does not have substring of three or more consecutive same symbol?
For example, I can't have ${baaab}$ nor ...
0
votes
2answers
42 views
Formal algorithm to test whether two given regular expressions define equal/identical or unequal languages
I'm trying to create a formal algorithm in order to determine whether
two given regular expressions $a$, $a'$ define identical/equal or
unequal languages and if those languages are subsets of each ...
0
votes
1answer
37 views
Can this DFA be converted to a regular expression? [duplicate]
I want to make the regular expression of this language but I can't: I tried but the regular expression didn't match some strings that it should. Is it even possible?
