Questions tagged [regular-expressions]

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

Filter by
Sorted by
Tagged with
-2
votes
1answer
76 views
1
vote
1answer
563 views

Regular Expression for {W | W contains an even number of As and an odd number of Bs, but doesn't contains AB}

While studying Automata at my University, I faced the following problem from SIPSER, M textbook: Consider D = { w | w contains an even number of as and an odd number of bs and doesn't contains the ...
1
vote
1answer
66 views

What does $k$ mean in regular expressions?

From what I have learned in Introduction to Automata Theory, Languages, and Computation, regular expressions can be represented with $R^{(k)}_{ij}$. I understand that $i$ and $j$ represent the ...
1
vote
0answers
52 views

Regular Expression Metric space

With Levenshtein distance we can create a metric space over string. Is there are any distance metrics for regular expressions?
1
vote
1answer
2k views

How to convert DFA to regular expression using arden's rule

I generally use state removal method to convert DFA to regular expressions. But I want to try other methods like using algebraic methods and arden's rule. How to solve a DFA with multiple final ...
0
votes
0answers
17 views

Language is regular via regular expression [duplicate]

I was wondering if this language is regular L={$a^{2m+k}b^{3n+l}c^{m+n}$ & $ k>2 $ & $ l \le 3$ & $m,n \in \mathbb{N}$} .I think the regular expression is : $(aa)^*aaa(a)^*(bbb)^* \...
1
vote
0answers
112 views

What is the correct regular expression for this language?

Consider the following problem: $L$ is the language of regular expression $00^*11^*$. $DM(L)$ is the language obtained from $L$ by throwing away every even-length string belonging to it and for each ...
3
votes
0answers
100 views

Algorithms to match regular expressions containing backreferences

I'm trying to come up with an implementation of a matcher for regular expressions containing backreferences like: ([a-c])x\1 which would match ...
0
votes
3answers
584 views

Conversion of FA to Regular Expression

If there is a transition with no input in the FA, when it is converted to a regular expression should it be accepted as ɛ transition? As an example picture shown below, should regular expression ...
1
vote
1answer
141 views

Does exist an algorithm to find all equivalence classes of given regular expression without kleene star? If yes then what is it?

Does exist an algorithm to find all equivalence classes of given regular expression without kleene star? If yes then what is it? Note that alphabet of the given regular expression is binary, i.e. it ...
9
votes
3answers
2k views

Is $(a^nb^m)^r$ regular?

I took my theory of computation exams a few weeks ago, and this was one of the questions: Assume language $L=\{(a^nb^m)^r \mid n,m,r\ge 0\}$ Is L regular? If yes provide a regular expression ...
2
votes
1answer
127 views

Is computing the cardinality of sum of regular expressions without kleene star closure EXPTIME problem?

Is computing the cardinality of sum of regular expressions without kleene star closure is EXPTIME problem? Note that sum of regular expressions is union of regular expressions. The alphabet of each ...
1
vote
2answers
1k views

Efficiently find smallest unique substring

Let's say we have a string $s$. We define a unique substring in $s$ as a substring that occurs only once in $s$. How can we efficiently find such a substring with the smallest length in $s$? The most ...
0
votes
1answer
237 views

How to generate regular expression for language of regular expressions?

Alphabets = $\{0, 1, \epsilon, \emptyset, [, ], \cup, \circ, \star\}$ where $\circ$ stands for concatenation, $\star$ is kleene star, $\epsilon$ is empty string, $[$ and $]$ are brackets to be used ...
1
vote
1answer
63 views

Is regular expression syntax regular?

Regular expressions are equivalent to DFA's and describe regular languages, but is the language used to construct regular expressions regular? My guess is that the original syntax (concat, | and *) ...
1
vote
3answers
184 views

Irregularity of language of words whose length is of power of 2 [duplicate]

How to show that the language containing the words whose length is a power of $2$, $L=\{w\mid|w|=2^i\}$, isn't regular using the pumping lemma? The pumping lemma says that Let be M a regular ...
-1
votes
1answer
41 views

Formal Languages - Matching this regular expression

I'm trying to write a regular expression over the alphabet {0,1,2} for the language in which every 1 is preceded by 0. For example 2200201010, 01022020102012 are strings of the language. I've tried ...
0
votes
1answer
645 views

Confusion converting BNF to regular expression

I have a Computer Science A-Level exam tomorrow and I've been trying to get this question answered by my teacher but she's not been too helpful so asking here instead. In an exam question, I have the ...
0
votes
1answer
35 views

Regular expression for the second symbols from the front and the back are equal

I am practicing for an exam. I am trying to convert a language to a regular expression. The language and my solution is as follows: $L=\{w∈\{a,b\}^+│|w|≥4\ and\ the\ second\ symbols\ from \ the \ ...
5
votes
0answers
209 views

How to disambiguate symbolic regular expressions

What I mean by a "symbolic regular expression" (if there already is a different name for this I'm not aware of it) is a regular expression that may include exponents that are symbolic arithmetic ...
0
votes
2answers
218 views

Prove that $L=\{a^i b^j c^k \mid i=1$ implies $j=k\}$ is NOT regular [duplicate]

Are there any closure properties which I can use to come up with a contradiction?
0
votes
2answers
103 views

Prove that the language { uw : |u| =2 |w| } is regular

I have a problem with this following question: Prove that the language $\{uw : |u|=2|w|\}$ is regular. I tried to give this regular expression $(uw²)^*$ to resolve it.
2
votes
0answers
349 views

Minimal regular expression that matches a given set of words

I have a dictionary-like regular expression, an "or chain" of words, word1|word2|word3|... Unfortunately, the chain is too large. I'd like to find the minimal ...
1
vote
1answer
112 views

Creating a Grammar that is equivalent to “RegEx A, RegEx B, or BOTH”

I have the following problem, create a Grammar on the Language {1,0} that accepts "strings with a length divisible by 3, or strings with a number of 0s divisible by 3, or BOTH". I created ...
3
votes
2answers
855 views

Converting REGEX to BNF grammar

Say I have a bunch of regex expressions which are used as filtering rules. (Any special extraction capabilities are unnecessary here, the set of regular expressions I have is only used for filtering ...
0
votes
0answers
118 views

Regular expressions for words avoiding aaa,bbb,ccc [duplicate]

I need to write a regular expression for all words over $\{a,b,c\}$ not containing $aaa$, $bbb$ or $ccc$. Will appreciate any help. Note: this is not homework.
1
vote
2answers
677 views

Drawing a DFA for a language/regular expression

how would you draw a DFA for the language over {a,b,c} of all words where every occurrence of b is preceded and followed by a. My thinking of this is that the regular expression for this is a* c* (...
-2
votes
1answer
42 views

Verification of regular expression computed from finite automata

Here in the given image, our question is to find regular expression from finite automata. I found three answers based on which state I am resolving. Are these answers in the photo correct? If any ...
1
vote
0answers
144 views

Regexp substitution and finite-state transducers

Many programming languages support a "regular expression substitution" operation: if r is a regular expression and s, ...
1
vote
1answer
37 views

Can a regular expression based “grammatic” be programatically minimized?

I have a list of pairs like (regex, substitute) that take quite long to apply to some input text so I was thinking about optimizing them a bit. From my knowledge for each regular expression there is ...
2
votes
2answers
150 views

Looking for an “intuitive” regular expression for $\{ w \in \Sigma^{\ast} \mid 2|w|_1 + |w|_0 \equiv 0 \pmod{3} \}$

Let $L \subseteq \Sigma^{\ast}$ with $\Sigma = \{0,1\}$ be the language such that two times the number of $1$'s in a word in $L$ plus the number of $0$'s is divisible by $3$, i.e. if we denote by $|w|...
1
vote
1answer
274 views

Writing a regular grammar for a regex of decimals

So I've got the regex /[1-9][0-9]*(\.[0-9]*[1-9])?/ and I'm trying to write a regular grammar for it. I started off like this: ...
-2
votes
1answer
53 views

What is the regular expression to match these conditions: there is atleast one (0), one (1), one (2) and does not end in (0)

I am lost on this and we a restricted to using flex/lex regular expression. I can easily do this with a lookahead predicate but i'm not allowed to use those. The does not end in (0) part is simple ...
1
vote
1answer
79 views

Question involving regular expressions

I've been playing around with converting regular languages to regular expressions and was wondering if my thinking is correct for this one. Question: The set of all strings that begin or end with ...
0
votes
2answers
933 views

Show that if A is regular so is $A^{R}$

I'm stuck on "For any language $A$, let $A^R = {w^R | w \in A}$ Show that if A is regular, so is $A^R$." According to my research (see references), the steps required to prove this question, are: ...
0
votes
4answers
311 views

How can every regex be accepted by an infinite number of finite automata?

In The (New) Turing Omnibus by A K Dewdney, chapter 2, it says: Moreover, for every regular expression there is an automaton which accepts the language symbolized by that expression. Thus, in a ...
0
votes
1answer
59 views

Explaining regular expressions

folks. My question is about explaining the each step of regular expressions. The task is to find the regular expression that contains 101 as a substring. I already know that the regular expression for ...
0
votes
0answers
17 views

Help with this FSA please :( [duplicate]

I have to convert this fsa to regular expression but these are too different than i learned... Can you guys help with converting these? Plz!
2
votes
0answers
243 views

What is a regular expression for solutions to the dog/cat/mouse river crossing puzzle?

This is a question that's been bugging me off and on for years, ever since I took a compiler theory class as an undergraduate. There, we learned how to convert a regular expression into a non-...
-2
votes
1answer
79 views

Formal languages - exercise

I'm trying to solve this exercise: given $L=\left\{a^kb^k|k>0\right\}$ determine $L^2$ and $L^3$. So I'm able to solve this kind of exercise if k is given into a defined range but I'm really ...
-3
votes
1answer
100 views

How to express the set of all ternary strings of odd length as regular expression?

I know that the lanuguage of all strings of odd length {a,b} can be expressed as: (a+b)((a+b)(a+b))^*. But what about an odd ...
12
votes
3answers
21k views

How to create DFA from regular expression without using NFA?

Objective is to create DFA from a regular expression and using "Regular exp>NFA>DFA conversion" is not an option. How should one go about doing that? I asked this question to our professor but he ...
2
votes
2answers
647 views

How to reduce this regular expression into DFA

$(a(aa|b)^*ab|b)((ba|a)(aa|b)^*ab|bb)^*((ba|a)(aa|b)^*)^*|a(aa|b)^*$ I know long algorithmic procedures but since regex is large I tried a lot by substituting common patterns for some regex ...
3
votes
2answers
151 views

Problems while trying to prove that $(r|s)^* = (r^*.s^*)^*$

I came across the following equality of regular expressions $$(r|s)^* = (r^*.s^*)^*\,,$$ where $r$ and $s$ are two regular expressions and $.$ denotes concatenation, but I don't know how could I prove ...
116
votes
4answers
152k views

How to convert finite automata to regular expressions?

Converting regular expressions into (minimal) NFA that accept the same language is easy with standard algorithms, e.g. Thompson's algorithm. The other direction seems to be more tedious, though, and ...
1
vote
0answers
23 views

Regular Expressions & Minimum DFA [duplicate]

Suppose that we have been given a regular expression $L$ and then we are asked to calculate the minimum number of states in the minimum sized DFA? How can we go about solving such questions? What I ...
1
vote
0answers
119 views

Regular Expression for All strings which contain no runs of a's of length greater than two.On L={a,b,c} [closed]

My attempt is We can fairly easily build an expression containing no a, one a, or one aa: (b+c)(€+a+aa)(b+c) but if we want to repeat this, we need to be sure to have at least one non-a between ...
8
votes
3answers
2k views

Why isn't it simple to count the number of words in a regular language?

Given a DFA, A, let L(A) denote the number of words A accepts. I think it's easy to calculate L(A): Translate the encoding of A into a regular expression. If the Kleene star appears anywhere in the ...
2
votes
1answer
45 views

Regular expression for a language which doesn't look regular

I'm trying to find a regular expression for the following language: $$L=\{x0y : \text{$x$ contains same number of 0's as $y$ contains 1's}\}. $$
1
vote
1answer
46 views

Can a machine choose whether or not to accept a state in a FSM

We were given a question in class with this FSM and had a debate over what the regex would be and the corresponding accepted strings. Does this FSM make sense as on state 1 there seems to be a choice ...