Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [regular-expressions]

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

0
votes
1answer
35 views

Regular expression of length n divisible by 2 or 3

I have an alphabet $\sum=\{o,g\}$ and I need to write a regular expression for arbitrary sequences of length $n$ where $n$ is divisible by 2 or 3. My guess would be [og][og]* | [og][og][og]*, but I ...
0
votes
1answer
20 views

Regular expression that represents the words s.t. start with $a$ and have an odd quantity of $a$'s

Find a regular expression that represents the language "The words over the alphabet $\{a,b,c\}$ such that end with a pair of letters, or start with $a$ and have in total an odd quantity of $a$'s". ...
-1
votes
0answers
10 views

Converting a regular expression into a NFA

The regular expression is: (00001 + 00100 + 0101)*(0 + 1). From my understanding, this means every string must end in a 0 or 1 and may be preceded by nothing or any number of 00001s, 00100s, or 0101s. ...
1
vote
0answers
35 views

Closure of regular languages to $A(L)=\{zyx|x,y,z \in \{0,1\}^*, xyz \in L\}$

Given: $A(L)=\{zyx|x,y,z \in \{0,1\}^*, xyz \in L\}$ Given $L \subseteq\{0,1\}^*$, Prove/Disprove: If $L$ is regular $\implies$ $A(L)$ is regular If $L$ is context free$\implies$ $A(L)$ ...
1
vote
1answer
17 views

+ (plus) notation in regular expression

I'm a student learning regular expression. today while studying I saw the question Regular expression (A*B*)* = (A+B)* proof. for me + notation means one or more, while * means zero or more. So $(A^*...
0
votes
1answer
75 views

Regular expression of L = {w ∈ {0, 1} ∗ | w does not contain 111}

I'm trying to find regular expression of L = {w ∈ {0, 1} ∗ | w does not contain 111}. I think there are many information about regular expression that does not contain the substring 110. but I think '...
0
votes
1answer
54 views

Regular Expression for $L = \{a^n b^m | n \geq 1, m \geq 1, nm \geq 3\}$

I'm trying to find a regular expression for $L = \{a^n b^m: n \ge 1, m \ge 1, nm \ge 3\}$ It's really hard for me to figure this out. can anybody please help?
1
vote
1answer
26 views

Not reachable accept state in DFA

I am trying to show that every deterministic complete finite automaton that recognizes the language $a^*b+b^*$ for $\Sigma = \{a,b\}$ contains a state $q$ such that no accept state can be reached from ...
0
votes
1answer
14 views

Suppose there always exist pairs of finite automata that recognize L and the complement of L, respectively. What does this imply?

Suppose there always exist pairs of finite automata that recognize L and the complement of L, respectively. What does this imply? my answer That all languages can be recognized by finite automata. ...
0
votes
0answers
33 views

Language to DFA

Be $F_k$ a language over $\Sigma = \{0, 1, \#\}$ of the form: $L_k = \{v\#uvw | u, v, e \in \{0, 1\}^*, |v| \leq k\}$. Show that for each k: $L_k$ is regular by constructing a DFA for $L_k$. The ...
0
votes
1answer
45 views

What is the regular expression for all bit strings with even number of 0's? [closed]

What is the regular expression for all bit strings with even number of 0's? Would it be: 0*(1*01*0)* And if so can you explain why, any help would be appreciated.
0
votes
0answers
20 views

Regular languages

I can't seem to understand this below : Is the language {a, ab} regular? Yes. We can write it as the product of the two regular languages {a} and {𝜆, b}: {a, ab} = {a}{𝜆, b} I would appreciate an ...
0
votes
0answers
34 views

Prove that every language with nonempty complement is contained in a regular language with nonempty complement

To clarify, the problem statement also specifies that the aforementioned regular language (let's call it R) is a proper subset of $\Sigma^*$ I'm not really sure how I should be approaching this ...
2
votes
1answer
54 views

language kleene star union not equal to union of language kleene star

Find languages A and B such that $A^* \cup B^* \neq (A \cup B)^*$. Is this even possible? I tried: $A:\{$ $\epsilon $ $\}$ and B:$\{$ $1$ $\}$ $A^*= \{\epsilon \}$ and $B^*=\{\epsilon,1,11,111,.......
0
votes
0answers
34 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 ...
0
votes
1answer
51 views

Pumping Lemma - unregular expression

How do prove that this expression is unregular, I know firstly you have to try prove that it is regular and work from there. I also know that $w=xuz$ and the three rules are needed Let $M$ be the ...
0
votes
0answers
34 views

Writing a regular expression to represent a set using Kleene stars

Here's the question: Let Σ = {a, b, c}. Write a regular expression for the set of all strings in Σ* (the * represents a Kleene star) such that the sum of the number of a’s and b’s in the string is at ...
0
votes
0answers
15 views

Find a regular expression to describe a set of strings of given length

For example if I want to find a regular expression to describe the set of strings over {a, b} with length of exactly 3 would I have to do something like this? $$(a \cup b)^3$$ But what about of ...
0
votes
0answers
28 views

number of words in language $L \subset \Sigma$

I had my lecture today about decidable languages and as I am reviewing the material I have from the university, I got quite confused about the following definition: $\emptyset$ doesn't contain any ...
1
vote
0answers
54 views

How would I go about proving that the language accepted by a regular expression is subset of the language accepted by a context free grammar?

Recursive cases: Let A, B be arbitrary RegExps and Let C$_{A}$, C$_{B}$ be cfg(A) and cfg(B) where the properties of cfg can be defined as: cfg($\phi$) = the CFG with no productions cfg($\epsilon$) =...
0
votes
1answer
127 views

Regex for bit string containing at least 2 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 consecutive zeros ...
4
votes
1answer
43 views

Regular Expression From a DFA

I am trying to create a finite automate that would accept any strings that have at least to 0s but reject all strings that have consecutive 0s. I have designed a deterministic finite automaton (DFA) ...
0
votes
1answer
168 views

Left Linear Grammer to Right Linear Grammer

I am learning Regular Grammar and given the problem to convert S->S10/0 from left linear to right linear grammar. I've seen examples of such conversions where we first write the reverse ...
2
votes
1answer
62 views

How to find the equivalence classes of a formal language complement?

Let $L=\{\sum^*-(\{\epsilon, a,b\}\cup \{bba^i|i\ge 0\})\}$ be a language over $\sum=\{a,b,c\}$. Find the equivalence classes of relation $R_L$ which is defined as follows: $xR_Ly \iff \forall z\in \...
2
votes
1answer
65 views

Is there a metric with wildcard?

Is it possible to define a metric over a set of elements $e=(x,y)$ where $x,y\in \{*,0,1\}$, $*$ being the wildcard symbol? For simplicity, assume all words of length 2, i.e. $0*$, $11$ and $**$. ...
2
votes
2answers
97 views

Proof for equivalence of two regular expressions

I have to show via equivalence transformation, that these two regular expressions are equivalent: $$(ab+b^*a^*) = (a+b^*)(a^*+b)$$ Can someone give me a hint how to show this? I am only allowed to ...
3
votes
1answer
40 views

Construct a regular expression

The problem asks me to construct a regular expression for the set of strings in {a,b}* that have even number of a and b. What I have tried is (aa)* + (bb)* + (aabb)* but I believe it does not cover a ...
0
votes
0answers
40 views

Proving 2 languages are equal.

I am quite new to Discrete Math and having lots of troubles solving the problems in it. Currently, I am struggling with a problem: Prove by induction that if $A$ and $B$ are regular expressions over ...
1
vote
2answers
88 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 ...
1
vote
1answer
44 views

Let $L_1$ be the language over alphabet $\{0, 1\}$ defined by $L_1 = \{x : \#_{01}(x) \bmod 3 = 0\}$. Give a regular expression that denotes $L_1$

Let $L_1$ be the language over alphabet $\{0, 1\}$ defined by $L_1 = \{x : \#_{01}(x) \bmod 3 = 0\}$. Give a regular expression that denotes $L_1$, and justify its correctness attempt Need 010101 ...
0
votes
1answer
24 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
1answer
28 views

What is the language of this regular expression $0^*$ concatenated with $1^* (0^*1^*$).

What is the language of this regular expression $0^*$ concatenated with $1^* (0^*1^*)$? $$ \begin{align} L(0^*1^*) &= L(0^*)L(1^*)\\ &= {λ, 0, 00, ...}{~λ, 1, 11, ...}\\ &= {λ, 0, 1, 01, ...
1
vote
1answer
191 views

If RS is equivalent to SR, then R*S* is equivalent to S*R* (Proof by Contradiction)

R and S are arbitrary regular expressions. I need a counter example where this is not true. I am unable to figure this out.
1
vote
1answer
22 views

How to write a regular expression over $\{a,b\}$ such that there're at least $3$ occurrences of adjacent different letters?

How to write a regular expression over $\sum=\{a,b\}$ such that there're at least $3$ occurrences of adjacent different letters? For example, $abab$ is a word in the language as is $babbbaaaaaba$. I ...
0
votes
1answer
69 views

Inductive Proof With Regular Expression

I'm trying to prove that the elements of the language $L((01+10)(01+10)^*)$ have an equal number of $0$'s and $1$'s. So far I've the base case: $R^n \to R^0 = 01 + 10$, all of which have equal number ...
1
vote
1answer
25 views

proof that a language is a regular according to another language

let $L\subseteq\Sigma^*$ be a regular language. for $\sigma \in \Sigma$ prove that $L'=\{w_1\sigma w_2:w_1w_2\in L\}$ is a regular languge. I tried induction on the length of the regular expression ...
0
votes
0answers
173 views

DFA conversion to Regular Expression using state elimination

I'm trying to convert my DFA (accepts any string not containing 00) to regular expression using state elimination but I'm a bit lost as to the whole thought process. My DFA: My regular expression: ...
1
vote
1answer
40 views

Regular expressions match not “abc”

I need to match any latin word NOT containing "abc" using basic regex operations (without syntactic sugar or look-ahead like (?!...)): only +, *, |. Solution for "ab" would be quite trivial, but ...
0
votes
1answer
40 views

Finding a regular expression for a given language

I'm told that given the alphabet {a,b} I have to find the regular expression for a language that has at most two a's I came up ...
3
votes
2answers
46 views

How Can The Following Language Possibly Be Regular?

$L =$ {$(01)^a$$x(10)^b$ | $a=b, b > 0, x∈${$0,1$}*} This is a question where according to the key, yes, the language is regular, but no explanation is given. However, if $a=b$, then this can be ...
2
votes
1answer
45 views

Help simplifying expression

I have the following set of equations: 1) $\text{$b_1$} \cos (\text{$\beta_1$} u)-\text{$b_1$} \cosh (\text{$\beta_1$} u)-\text{$b2$} \cos (\text{$\beta_1$} \theta y)-\text{$d_2$} \cosh (\text{$\...
0
votes
0answers
35 views

How to Express A Regex That Accepts Nothing

I'm asked to write a regex that accepts the complement of another given regex: (a*b*)* This regex seems to accept every single string on the alphabet consisting ...
2
votes
1answer
54 views

What's wrong with this proof? (Regular languages)

We want to show that for any fixed $n$, $\bigcup_{i=1}^n L_i$ is regular when all $L_i$ are regular. I understand that this is only true for finite $n$. However, what's wrong with the following ...
0
votes
1answer
240 views

Regular Language and Non-Regular Language

Regular Language as I know of, is something that can be defined by a FSM. Non-Regular Language is something that consists of repetition which cannot be stored by the FSM. I have found out that L( ...
0
votes
1answer
101 views

Show that the regular expressions (a+b)* and (a*b*)* are equal.

Let $L_1 = L((a+b)^*)$ and $L_2 = L((a^*b^*)^*)$. I need to show that $w \in L_1 \Rightarrow w \in L_2$. I have already done the $\supseteq$ direction. Here's what I did: Suppose $w \in L_1$. If $w =...
0
votes
1answer
33 views

What does the “?” mean in generated language grammar?

I know $a^*$ means that a string could be composed of zero to infinite $a$'s, and $a^+$ means one or more $a$'s. But the professor posted this question... Given the regular expression $b?a(a|b)ab?$...
2
votes
1answer
51 views

String powers. Lemma 1.3.5 in word processing in groups. Epstein.

I can't understand this demonstration. Why if ${w'}_1$ is different from ´${w'}_2$ then we have that $f(u)$ and $v'$ are powers of some string $z$?
2
votes
1answer
38 views

What is open first in formal languages

What is a set of values that come from $(1^*0^*)^*$? Is it set of any number of combinations of any number of 1 and any number of 0. Like we have 10 inside of brackets and than repeat it as much as ...
2
votes
1answer
46 views

Given a finite automaton determine if it is deterministic and indicate regular expression

Given the finite automaton: Make the transition table and indicate if it is deterministic or not. Indicate which of the following regular expressions corresponds to the language recognized by the ...
0
votes
0answers
67 views

Regular set definition

I came across the following regular sets definition: Let Σ be a finite alphabet. Regular sets over Σ are defined recursively as follows: ∅ (i. e. an empty set) is a regular set over Σ, {...