# Questions tagged [regular-expressions]

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

492 questions
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 ...
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". ...
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. ...
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)$ ...
1answer
17 views

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 ...
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 ...
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 ...
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 ...
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 ...
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$) =...
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 ...
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) ...
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 ...
1answer
62 views

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{$\...
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 ...
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 ...
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( ...
1answer
101 views

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 ...
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 Σ, {...