Questions tagged [regular-expressions]
Questions about regular expressions, a formalism to describe regular languages.
724
questions
0
votes
0answers
15 views
I cant figure out which regular experesion solves my problem [duplicate]
The language L=a binary number with even number of digits that doesnt have 2 consecutive zeroes.
What is the regular expression that can search those words and how what is your thought process when ...
2
votes
1answer
29 views
Convert a dfa to rule for a asterisk case
Here is a simple but very common grammar rule case in EBNF format, the Statements is a none terminal symbol and Statement is ...
0
votes
1answer
25 views
Can any language be expressed by regular expression?
I'm studying Autoamta Theory currently and am wondering if any Language (for example Lanugage L in Alphabet A={a,b}) can be expressed by regular expression.
In my current understanding the rule is &...
0
votes
0answers
18 views
Structural induction proofs for regular expression [closed]
Let $RE$ be the set of regular expressions over the alphabet {a,b}
How do I go about proving the following using structural induction
For each r $\in$ $RE$ there is a $r'$ in $RE$ such that $\epsilon$ ...
0
votes
1answer
22 views
Empty string in an ambiguous grammar?
I'm a bit confused by the role of the empty string in this ambiguous grammar:
A' -> A
A -> if A B
A -> null
B -> [empty string]
B -> else S
So what ...
0
votes
1answer
22 views
Can a non-regular language have a regular grammar?
Basically the title. I am supposed to find a regular grammar for the language that produces palindromes. This is all I have right now:
S -> 1 | 0 | ε
Since it ...
-2
votes
0answers
50 views
Regular grammar for language that does not contain "abab"
I tried this :
$V = \{S,A,B\}$ and $T = \{a,b\}$.
$S \rightarrow aS | \epsilon | abaAS | BS$
$A \rightarrow a | aA$
$B \rightarrow bB | \epsilon$
Any thoughts/objections?
1
vote
1answer
29 views
Regular expression for set of all strings containing no 3 consecutive 0s?
The answer is
$1^*01^*01^*+1^*(0+00+\in)1^*$
If I had to rephrase my question, it would be how to approach regular expression problems? Is it all about practice?
How do I understand what the regular ...
3
votes
2answers
554 views
Regular Expressions - What is difference between a+ and a⁺
I'm very confused as to if a+ and a⁺ mean the same thing or are completely different.
0
votes
0answers
38 views
conversion of regular expression to automata
I've a task to specify a finite automata (of any kind) that accepts the language described by this regular expression: $a(bab)^+b^*|(ab)^*(aa)^+$
My first solution looks like this:
I would like to ...
1
vote
1answer
28 views
Regular expression for words without two equal consecutive letters
I need to find a regular expression for the language over $\{a,b,c\}$ consisting of all words in which no two consecutive letters are the same.
For example, $abacbabca$ is in the language, while $abbc$...
2
votes
1answer
39 views
Are Nondeterministic Finite Automata not allowed 'sink-states'?
By definition are Nondeterministic Finite Automata not allowed a 'sink-state' (non-accepting state we don't get out of)? I can see us having them for NFA but not necessary but do not see how they are ...
1
vote
1answer
28 views
How to interpret the regular expression 0*10|01(01)*?
I'm having some trouble understanding the regular expression $0^*10|01(01)^*$.
The expression matches strings like $00010$. But for some reason, I wasn't able to find a string that matches the $(01)^*$...
1
vote
1answer
38 views
set theory with RegEx on fen strings (or another parser)
how can you find if a regex call is a subset of another regex call on an predictable set of data
I have a string (chess Forsyth–Edwards Notation (FEN) string...
2
votes
2answers
56 views
If L is regular so is the language of compressed doubles
Suppose L is a regular language over the alphabet $\Sigma$. I need to prove that
$$ L'=\{x_0\cdots x_n:x_0x_0x_1x_1\cdots x_nx_n\in L, \ \ x_i\in \Sigma\}$$
I thought I could take a DFA which computes ...
0
votes
1answer
29 views
Convert regex pattern to LL1 parser
Background: I'm trying to solve this leetcode problem: regular-expression-matching. My approach is to implement a LL(1) parser generator, might be overkilling for this problem but it's just a brain ...
1
vote
1answer
24 views
Regular expression for all a* except aa?
I'm stumped on how you would describe a language which is a* except for aa, so the following is acceptable:
a
aaa
aaaa
aaaaa
...
It's for part of the below DFA
1
vote
1answer
71 views
I have found an example where regular expression is not closed under concatenation. Where am I wrong?
$a^n$ is a regular expression.
$b^n$ is a regular expression.
their concatenation is $a^nb^n$ which is not a regular expression.
1
vote
1answer
63 views
How to write a regex for repeated patterns
I have an alphabet $\Sigma = \{a,b,\#\}$. I'm trying to write a regex that only accepts strings that have the same pattern before and after the $\#$ without using back references. For example, $aab\#...
0
votes
0answers
32 views
Regular expression for all words over $\Sigma$ in which at least one symbol is missing [duplicate]
I have to consider the language $L$ on the alphabet {a,b,c,d}$ given by the words where at least one symbol of the alphabet is missing.
For example: abcccaca and bdadadaddb are accepted, but ...
0
votes
0answers
25 views
DFA and RE find out the language. Please can you explain?
Find the regular expression describing following languages over alphabet {0, 1}*.
...
1
vote
1answer
151 views
What is the regular expression for the language, {w | w does not contain the substring 11}
{w | w does not contain the substring 11}
What I am thinking: $(0^* 1 0^* )^*$
Is anything wrong with my expression?
Thanks in advance for your help!
0
votes
1answer
45 views
Simplifying the Language of this DFA
Above's the DFA in question (Sipser, Page 36). I have obtained the language of this DFA to be 0*1(1+00+01)*. But Sipser's textbook goes on to explain that the language of this DFA is (0+1)*1(00)*. But ...
1
vote
0answers
25 views
Is non-equivalence of regular expressions with union, concatenation and squaring NEXPTIME-hard?
On wikipedia, page about EXPSPACE it says
An example of an EXPSPACE-complete problem is the problem of recognizing whether two regular expressions represent different languages, where the expressions ...
0
votes
0answers
34 views
Is my regular expression correct for this question?
IBM has decided that all sequences of numbers (such as mobile numbers) must be ordered in such a way that any mobile number is followed by at least 2 corporate numbers, and any landline number is ...
-1
votes
1answer
43 views
High Level description of Turing Machines
How can create a Turing machine that checks whether or not an input string is a well-defined regular expression? For example, it recognizes a language that consists of string over {0,1} and the ...
0
votes
0answers
58 views
Are the regular expressions equivalent?
Is the following equivalence true?
$$(r_1^*r_2^*)^* = (r_1 + r_2)^*$$
I think these are equivalent since both the expressions generate the same strings: $\{\epsilon,r_1,r_2,\dots\}$ etc.
-1
votes
2answers
47 views
Are this languages can be represented by regular expressions?
The set of all words with the same number of 0’s and 1’s.
The set of all words contained in {0,1}* that have an even number of 0’s and an odd number of 1’s.
I guess first one is NO.
Second one seems ...
-1
votes
1answer
27 views
How do I solve regular expression expansion when I have "+" sign?
For example, I am given this and my output is:
11+11* = 11, 1, 11, 111, 1111, ......
Since + means or sign, my logic is:
11 appears once or more
Then I work on solving 11*
Is it perfect?
Thanks.
0
votes
1answer
30 views
Does finding a reversal of a regular expression by automata need automata to be a DFA?
If I want to find the reversal of a regular expression using an automata, Do I have to transform the automata to DFA if it wasn't ?
0
votes
1answer
73 views
Which of the following languages can be represented by regular expressions?
The set of all words contained in $\{0,1\}^*$ that have an even number of 0’s and an odd number of 1’s.
I came to discover that it is possible but not sure how. Can anyone express it in a regular ...
0
votes
0answers
46 views
How to carry out expansion in regular expression problems like ((0*10)*)?
I have been given some problems like:
Determine if each of the following strings belongs to the corresponding regular language.
i. ‘10100010’ and L((0*10)*).
iv. ‘011100101’ and L(01*10*(11*0)*)
I ...
2
votes
1answer
29 views
Minimal state DFAs for a regular expression of length $n$
I know that given any regular expression, we can find always find a minimal DFA which accepts the language it describes. However, this process can take up to exponential time and space. I'm wondering ...
0
votes
1answer
72 views
Simplify $R:=0^*+0^*1\left(1+000^*1\right)^*0^*$
I'm trying to simplify the following REGEX:
$$R:=0^*+0^*1\left(1+000^*1\right)^*0^*$$
$R$ is the result of transforming a GNFA that recognizes $L:= \{w \in \{0,1\}^* | \left(\forall \ i \in \left[1,|w|...
0
votes
1answer
47 views
Prove $(aa^*bb^*)^*=ϵ+a(a+b)^*b$ using regex laws
I tried to prove this by starting at RHS:
$$ϵ+a(a+b)^*b = ϵ+a(a^*b^*)^*b$$
But I dont know how to convert $(a^*b^*)^*$ to something else that will be helpful.
Any ideas?
1
vote
2answers
74 views
An integer (a string of digits) is $\text{/[0-9][0-9]$\ast$/}$. (Why isn't it just $\text{/[0-9]$\ast$/}$?)
I am currently studying the textbook Speech and Language Processing, 3rd edition (draft), by Jurafsky and Martin. Chapter 2.1.1 Basic Regular Expression Patterns says the following:
The regular ...
-3
votes
1answer
65 views
How can I convert from DFA in to regular grammar?
I have following information.
0 1
-> *q0 q0 q1
q1 q1 q2
q2 q2 q0
I have to convert this in to a regular grammar.
I wrote this:
...
-3
votes
1answer
41 views
How can I convert a Grammar to NFA?
Hello I have a task where I´m stucking at.
I have to convert a Grammar to NFA. I have these information:
G=(V,T,P,S) V={S}, T{0} and
S -> 0S
S -> 0
I can´t ...
0
votes
1answer
98 views
How to describe the language of an automaton in plain English?
How do I describe the following automaton in plain English?
The only thing that I can think about when explaining in plain English would be the states, alphabet, start, accepting state, but I think ...
0
votes
1answer
23 views
Simplification of regex
I have a regex $R=\epsilon+1+(\epsilon+1)(\epsilon+1)^*(\epsilon+1)$ which has to be simplified by algebraic operations. As we can do,
$\epsilon+1+(\epsilon+1)(\epsilon+1)^*(\epsilon+1)=\epsilon+1+(\...
1
vote
3answers
96 views
Proving $(a + ab)^*a = a(a + ba)^*$
Need to prove $(a + ab)^*a = a(a + ba)^*$ by using regular algebra.
Concatenation does not commute. So repeated use of commutativity will fail. I am getting confused about which identity I should use ...
0
votes
0answers
34 views
Regular identity proof or disproof
I have to prove or disprove the following identities:
$(RS+R)^*RS=(RR^*S)^*$
$(R+S)^*S=(R^*S)^*$
$S(RS+S)^*R=RR^*S(RR^*S)^*$
So what I tried:
Not same because LHS cannot generate $\epsilon$ while ...
0
votes
1answer
53 views
Describe regular expression
I am learning about regular expression, and trying to describe a regular expression for the language L
$\qquad L = \{a^i b^j c^k \mid i+j = k\}$
What is the right approach and how to describe a ...
1
vote
1answer
149 views
Regex for strings with even number of 1's and number of 0's divisible by 5
I was trying to build up this regex but I am having huge expressions but nothing generates the given regex. I tried to break up the regex as
$0$ multiple of five times and odd $1$'s
$0$ multiple of ...
0
votes
1answer
32 views
Regular expression for the language accepting the strings containing at most one pair of $1$'s over $\{0,1\}$
Design a regular expression for the language accepting the strings containing at most one pair of $1$'s over $\{0,1\}$
So basically we have the language $L=\{11,011,110,0011,1100\ldots\}$.
I find the ...
0
votes
1answer
19 views
Regular set corresponding to regular language
I have just started learning regular expressions and I don't have anybody around me to help me building conceptions. So I rely on online mediums. My question is whether every regular set corresponds ...
5
votes
1answer
81 views
Can a non-regular language $L$ have a non regular $L^*$?
I have been looking around and i cant seem to find an example of such case that a non-regular $L$ has a non regular $L^*$. Is it possible? If so, can you provide an example of such case please?
0
votes
3answers
139 views
How many languages are described by a regular expression?
How many languages can a Regular Expression describe is it only one or infinite?
I have tried to google it but i haven't found any answer?
I know that a Regular Expression describes a Regular Language?...
0
votes
1answer
30 views
Conditions for an Language to be infinite
given 'r' , a regular expression that does not include λ or ∅, What are the Conditions of 'r' so that L(r) would be infinite?
-1
votes
1answer
37 views
Prove that given 2 regular expressions represent the same language
Is it possible to use regular expression identities to prove or disprove that the RE1=0*(0+1)*0* and RE2=(0+1)* represent the ...
