# Questions tagged [regular-expressions]

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

519 questions
Filter by
Sorted by
Tagged with
12 views

### Regular expressions for some languages [duplicate]

Set of strings over $\{0,1\}$ having at least two occurrence of the substring 00. $\{a^n b^m : n ≥ 4, m ≥ 3\}$. Set of strings over the alphabet $\{a,b,c\}$ containing at least one $a$ and one $b$.
182 views

### Are regular expressions a*a and aa* equivalent?

Let $\Sigma = \{a, b\}$ an alphabet. Are the regular expressions $a^*a$ and $aa^*$ over $\Sigma$ equivalent? Even though concatenation is not commutative, in this case it seems like the statement is ...
38 views

### construct regular expression for a language [duplicate]

I want a regular expression for the following language. (a+b+c)*, but does not contain substring "abab". That means it can be any combination of (a, b, c) except "abab". I tryed to construct it ...
421 views

### What parts of a programming language can't be defined using Regular Expressions?

I'm trying to understand how the syntax of some programming language is defined. I know that there are some parts of the syntax of programming languages that can't be defined using regular ...
56 views

### DFA & RE from descriptive definition of given regular language

I am trying to make the DFA and RE of a regular language which is define on the alphabet = {1,0} and all the strings present in these languages have exactly one 010 substring in them. Some strings ...
179 views

45 views

### How to use homomophism in closure proofs?

I am having a hard time understanding homomorphism. All I seem to understand is that it is a substitution. When I look at examples of proving closure of a particular operation over a regular language, ...
45 views

### Maximum number of words in deterministic finished automata with k-states [closed]

I have exercise: We have a given finished deterministic automata. It has 5 states and is based on the alphabet {a, b, c}. It can create n different words (we assume that n < inf). What maximum ...
43 views

### Difference between methods of converting from finite state machine to regular expression

I have a question about method that I saw on internet and method that my professor showed me. I have this finite state machine: ...
60 views

### Why is this not recognized by a DFA?

I am still confused over my professor's explanation on why this problem is not a DFA. The Problem: Explain why $L = \{p^kq^k \mid k>0\}$ cannot be recognized by a DFA My professor explained it as ...
40 views

23 views

### Formal Class of Languages Describable by .NET Regular Expressions

This is sort of a computer science question and sort of a programming question. What is the name of the formal class of languages that can be described by .NET regular expressions (assuming it a well ...
1k views

### Regular expressions and 'capturing parentheses' with 'backreferences'

We know that regular expressions (RE) are implemented with finite automata (FA). In some language (like JavaScript) in RE there are features like 'capturing parenthesis' with 'backreferences': https:/...
63 views

### Regular expression over alphabet A = {0 , 1, 2} for words that contain at least one 0 and don't contain 11

I got that I can get (1) followed by not (1) like this $$(0+2)^*1(0+2)^*$$ From this point I'm actually stuck. I can't set the (0) to be somewhere in expression. The only expressions I get are ...
427 views

### Regex for bit strings with at least two 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 ...
81 views

### In RegExr, why is regex OR in JavaScript sometimes not commutative?

On https://regexr.com/, using the default JavaScript (Browser) engine, the languages $L(a^*|b^*)$ and $L(b^*|a^*)$ are not the same. The first one matches only $a$'s and the second one $b$'s. Is ...
130 views

### Is this concatenation of two FA done right?

$r_3=r_1r_2=(a^*b)^*(a+ba)^*bb(a+b)^*$ comes out to be $r_3=r_2=(a+ba)^*bb(a+b)^*$ when i generate the resultant FA and its regex after concatenation i.e. it doesn't include $r_1$ Details: Consider ...
40 views

### Subset of a regular language, for each of whose words there exists an element with the same number of 1s in the other regular language

For regular languages $A,B\subseteq\{0,1\}^*$, is $$L_2 = \{x \in A \mid \exists y \in B : |x|_1 =|y|_1 \}$$ regular, where $|x|_1$ means the number of appearances of 1 in the word $x$? i need to ...
763 views

### Language of all strings that has exactly 1 triple b

I am new to automata and learning to make regular expression for languages. But I have been stuck on this one. Suppose we have a language L, Language of all strings that has exactly 1 triple “b” ...