Questions tagged [regular-expressions]

Regular expressions or Regex is a search pattern for strings defined by a sequence of characters.

Filter by
Sorted by
Tagged with
0
votes
0answers
8 views

Converting a regular expression to a grammar and regular grammar

I tried looking around for help before posting this but either the question did not match mine or I was not able to understand the answer posted due to my lack of knowledge. I am working on a lab and ...
0
votes
0answers
11 views

Prove or disprove that the language L is regular [duplicate]

I had an exam where I had to prove or disprove that the language $L=\{w^{|w|} | w \in \Sigma^*\}$ where $\Sigma = \{0,1\}$ is regular. On a glance, it looked regular to me so I tried using induction ...
1
vote
1answer
26 views

How do I convert a 5-tuple NFA to a diagram?

The only information I have is a nondeterministic finite automaton $(K, \Sigma, \Delta, s, F)$ where: $$K = {p, q, r}\ \Sigma = {a, b, c}\ s = p\ F = {q}\ \Delta = {(p, a, q), (q, b
2
votes
1answer
181 views

Give a regular expression for the set of strings over {a, b, c} such that the number of a's equals the number of b's and is equal to 2

How would I describe from finite automata to regular expressions? I know how I would describe it if there were to be just one or more number of a's and b's using + but I'm not sure how to go about it ...
2
votes
1answer
39 views

Regular Expression describing language accepted by Finite State Automata

Hopefully I am including the image correctly or this won't make any sense. I am trying to figure out a regular expression for what this FSA accepts. From what I can tell it accepts any combination ...
0
votes
1answer
76 views

Regular expression that accept the language of all binary strings with exactly two $a$’s and at least one $b$.

I need to design a regular expression that accept the language of all binary strings with exactly two a’s and at least one b. Here's what I've got so far: $(aab^+) \cup (ab^+a) \cup (b^+aa) \cup (ab^+...
0
votes
1answer
16 views

Context free grammar for language $\{ \{a,b\}^*$: where the number of $a$'s is unequal to the number of $b$'s$\}$

I've seen many solutions for when the number of $a$'s and $b$'s ARE equal but how should the grammar be for the time when the numbers are unequal? So far I have this but it can't produce many things ...
0
votes
0answers
9 views

Cumulative Regular Expression-ish Matching Problem

The problem is as follows: We have buckets numbered from 1 to N each with a tag. A tag can consist of characters from an arbitrary alphabet, or * and %. We can send tags to select buckets, a tag works ...
1
vote
1answer
11 views

How to transform a regular expression into a context free grammar with 2 variables?

I'm tasked with transforming this regular expression $((0+1)(0+1)^*(0+1))^*$ into a context free grammar. As an added constraint I'm must do so with a maximum of 2 variables. This is what I did : <...
0
votes
1answer
21 views

In regular expressions for regular languages, is there distinction between eager and lazy matching?

In regex, matching is eager by default, and lazy by ?. For example *abc and *?abc. In ...
0
votes
1answer
40 views

Can DFA's be directly constructed from some special regular expressions but not from general regular expressions?

Ullman's Introduction to Automata, Languages and Computation constructs a NFA from a regular expression and then a DFA from the NFA. Cormen's Introduction to Algorithms has Section 32.3 for string ...
2
votes
2answers
36 views

Do lookahead and lookbehind in regex come from some type of formal languages?

Real-world regexs are extensions of regular expressions in formal languages. Do lookahead and lookbehind come from some type of formal languages? (I suspected lookahead in LR(k) grammars, simply ...
1
vote
1answer
57 views

Why can regular expressions be defined without mentioning closure under intersection with regular sets, homorphisms, and inverse of homomorphisms?

The family of regular sets is the smallest full trio (closed under intersection with regular sets, homomorphisms, and inverse of homomorphisms) and also the smallest full AFL (closed under union, ...
2
votes
1answer
30 views

Is an alphabet necessarily a regular language over it?

The definition of regular expressions says they are closed under union, concatenation, and Kleene star. Single symbols also form regular expressions/languages. Since union is between two languages, ...
0
votes
1answer
27 views

How to build unambiguous binary expression with property

Is there a strategy for building unambiguous binary expressions that fit some property like "no consecutive 1's", "can't start with 0", "Blocks of 1 can only be divisible by 5&...
1
vote
1answer
35 views

What would the notation for this binary string look like?

Every block of 1's of length $\ge 4$ cannot be followed by a block of 0's of length $\ge 4$, and any block of 1s of length 1, 2 or 3 must be followed by a block of 0s whose length is congruent to 1 ...
1
vote
0answers
27 views

Is this automaton correct for this regular laguage?

The language in question is given by the regular expression $ab^*a$.
0
votes
1answer
21 views

Regular expression for languages with limit on repeated letters

I'm working through some mathematical Regex questions and I was wondering if you could review some of my answers. (1) L={w ∈ {0,1}* | w contains at least three repeated 1s} ...
0
votes
1answer
32 views

Regex with a limit on repeated letters

L={s ∈ {X, Y, Z, K}*|s doesn't include 5 consecutive Ks} How can I represent this in a regular expression? Specifically, how would I restrict the number of certain letter appearing repeatedly in a ...
0
votes
0answers
20 views

Kleene closure of a disjunctive normal form for regular expressions

$\newcommand{\Kstar}[1]{#1^\ast}$ I would like to write the regular expression $$ a^\ast b^\ast + ( a + b )^\ast b a ( a + b )^\ast $$ as a Kleene closure of a union of catenations or in other words, ...
0
votes
0answers
28 views

Regular expression without subword 000 [duplicate]

what is the regular expression for the language above {0,1} that does not contain the subword 000? Thank you for your help!!
0
votes
1answer
12 views

equivalence of regular expression: $L(\alpha\emptyset) = L(\emptyset)$

I need some help writing the proof for $L(\alpha\emptyset) = L(\emptyset)$ where $\alpha$ ist a regular epression and $L\widehat{=}$Language. What I have done so far: $L(\alpha\emptyset)=L(\alpha)...
-2
votes
1answer
58 views

What is the regular expression of the language accepted by the following NFA? [closed]

https://www.dropbox.com/s/dyy3m5m5bvhj1rt/NFA1.jpg?dl=0 This is the NFA. RE = (aa + ab) a* ((ba+bb) a*) * This is the solution i came up with but i'm looking for an optimal solution.
2
votes
1answer
39 views

Converting a regular expression to its complement via automata

I'm supposed to convert a regular expression $r = (\alpha\beta + \beta\alpha)^\ast$ into its complement via automata. I started out by first constructing the individual DFAs that recognize $\alpha\...
2
votes
1answer
60 views

A bijection between all regular expressions of alphabet $\Sigma$ and the natural numbers $\mathbb N$

I have been asked to form a method for enumerating all regular expressions generated by the finite alphabet $\Sigma$, denoted by $\newcommand{\RE}{\operatorname{RE}}\RE(\Sigma)$. The set of all ...
0
votes
0answers
52 views

Defining prefixes for regular expressions

When dealing with this question, I came to realize that I'm not sure how sensible it is to define prefixes for regular expressions. So far I've run into two sorts of prefix definitions, one for ...
2
votes
1answer
48 views

Showing that the language of prefixes $\operatorname{pre}\mathcal L$ is regular by using the definition of a regular language

A language is regular, if it is generated by a regular expression, meaning the expression consists of the alphabet $\Sigma_{\mathrm{RE}} = \Sigma \cup \{\epsilon, \varnothing, +,\ast,(, )\}$, and is ...
2
votes
1answer
78 views

Are regular expressions sets?

I have a confusion concerning regular expressions and languages generated by them. In our course material, regular expressions are defined as follows. If $\Sigma$ is an alphabet, regular ...
-2
votes
1answer
33 views

Prove $(L^*)^*=L^*$

https://i.stack.imgur.com/XJqT4.png How would I do this? I have tried to think of a solution but nothing comes to my mind.
0
votes
1answer
44 views

Is any anagram of the empty language the same as the empty language?

Given a regular expression r, r~ contains all anagrams of r. L(r) is the language accepting all words that can be constructed from r. E.g. Given the language L(r) = {dog}, L(r~) = {dog,god,odg,ogd,...
0
votes
1answer
32 views

Please help me understand these kind of Regular Expressions design

I've done my research for a while, read some chapters on books about it, and I can't for the life of me resolve these problems. I have read the rules of this kind of algebra. My teacher teaches this ...
1
vote
1answer
40 views

How can I prove that all strings in {0, 1} * that contain any palindrome of length at least 6 as a substring is regular?

Because palindrome is irregular, I do not know how to prove above, even if I know for example, {0^n1^n|n>0} is irregular but it is a subset of 0*1*, which is regular. I don't think I can use, for ...
1
vote
1answer
26 views

What does the “\” mean in this statement about regular languages?

I have having difficulty finding the meaning of the backslash in the statement. I don't know if it could be a division, an OR operator or something else. If someone could provide information about it, ...
0
votes
1answer
19 views

How to proof regular/non-regular with Nerode Theorem

$L_{1}=\left\{w \in\{a, b\}^{*} | \#_{a}(w)=0\right\}$ $L_{2}=\left\{w \in\{0,1\}^{*} | w=u v u \text { with } u, v \in\{0,1\}^{*}\right\}$ I'm trying to learn to proof regularity/non-regularity ...
1
vote
1answer
56 views

What kind of language is $\{\text{bin}(n)\text{oct}(n)^R \colon n \in \mathbb{N} \}$? Regular? Context-free? Neither? Prove.

I need to determine if the $L$ is: regular context free but not regular None of the above $$ L =\{\text{bin}(n)\text{oct}(n)^R \colon n \in \mathbb{N} \}$$ To do that, I chose this word: $$\text{...
2
votes
1answer
41 views

Is this language regular? $L = \{ xyyz \in \{0,1 \}^* \colon x,z \in \{0,1 \}^*, y \in \{0, 1\}^+\}$

I need to come up with a hypothesis and prove whether the language in question is regular (e.g. pump it out / provide a DFA that generates it). $$L = \{ xyyz \in \{0,1 \}^* \colon x,z \in \{0,1 \}^*, ...
0
votes
2answers
213 views

If we remove one string from any nonempty regular set, the resulting set is still regular.

I am guessing this is true, because based on the definition of a regular language: "A language is called a regular language if some finite automaton recognizes it". Meaning if we have a non empty ...
1
vote
1answer
51 views

Simplifying a regular expression

I'm trying to solve a problem that requires me to simplify regular expressions. Here is the starting point: $(aaa)^*b(bbb)^*$ Which I rewrote as follows: $(a^3)^*b(b^3)^*$ However I've been ...
0
votes
0answers
25 views

Regular expression of the Language over {0,1} where any prefix that ends with 00 does not contain 11

I need to find a regular expression of the strings over {1,0} where any prefix that ends with 00 does not contain 11 I was able to find when no 11's 00. But don't understand how to move forward.
1
vote
0answers
33 views

Can a regular language be defined using recursive regular expressions?

My problem is essentially that I can't find anything that explicitly prohibits or allows such definitions. To illustrate with an example: Our teacher challenged us to create a definition for a ...
0
votes
1answer
19 views

What do the regular expression operations + and . mean in the context of finite state automata?

Suppose you have the alphabet $\Sigma = \{0, 1, 2, 5\}$ where the symbols represent the value of coins, and you're given the regular expression $e = (1.1) + 2$ which is supposed to describe all the ...
0
votes
0answers
40 views

A regular expression that has a even number of a's and that does not contain the pattern aba

The problem I have is that for the language {a, b} I have to provide a regular expression that has an even number of a's and that does not contain the pattern aba. I know that for an even number of a'...
0
votes
0answers
28 views

Given the language $L=\{w\in\{a,b\}^*\mid\text{$w$ has an odd quantity of $a$ and even quantity of $b$}\}$ answer [duplicate]

Find a finite automaton that recognizes the language $$L=\{w\in\{a,b\}^*\mid\text{$w$ has an odd quantity of $a$ and an even quantity of $b$}\}.$$ Indicate whether the automata is deterministic or not....
1
vote
1answer
20 views

Find automata for $S\to01X\mid0S,\;X\to2X\mid1Y,\;Y\to2Y2\mid0$

Given the grammar $G=(\{S,X,Y\},\{0,1,2\},P,S)$ where $P$ is $$S\to01X\mid0S,\quad X\to2X\mid1Y,\quad Y\to2Y2\mid0$$ find the automata. The teacher found that the language generated by $G$ i.e. $L(G)$...
2
votes
0answers
19 views

Proving regular expression identity [duplicate]

For regular expressions $r$ and $s$ prove: $$(r^*s^*)^*=(r+s)^*$$ I guess I have to prove the equality of sets $(R^*S^*)^* = \left\{ x_1^{n_1}y_1^{m_1}x_2^{n_2}y_2^{m_2}... \mid n_i,m_j \in \mathbb{...
1
vote
1answer
30 views

Are the following regular expressions equivalent?

Is $$ 0((01+0)^+(0+10)1) = ((0+01)^+(01+101))^+1?$$ I think it's not , because the language generated by the regular expression on the left accepts the word 00101, but the language on the right doesn'...
1
vote
1answer
31 views

Creating DFAs from REGEX

I am currently studying DFAs and attempting to create a DFA that only allows strings that contain 'A' three times over the language ['A','B','C']. I have the following regex which is probably not ...
0
votes
1answer
37 views

Help with Regular Expression

How would you write a regular expression that matches exactly the strings over the alphabet {A, . . . , Z} that contains the letter "O" only if they contain the letter "I" and contain at most two "E"’...
2
votes
2answers
45 views

Proving the regular expression identity $(a(a + b)^*)^* = (ab^*)^*$

I'm struggling to prove the regular expression identity $$(a(a+b)^*)^* = (ab^*)^*$$ The recommendation is to use induction on the star operator. My strategy was to first prove that $$(a(a+b)^*)^* \...
1
vote
1answer
65 views

Check if two regular expressions are equivalent

I thought I proved that those two regular expressions are and identity using induction. But my friend told me that there was a counterexample. I am not sure anymore. $$(1(1 + 0)^*)^* = (10^*)^*$$

1
2 3 4 5
12