Questions tagged [regular-expressions]

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

Filter by
Sorted by
Tagged with
-2
votes
1answer
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$.
1
vote
1answer
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 ...
0
votes
0answers
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 ...
2
votes
3answers
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 ...
1
vote
2answers
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 ...
2
votes
2answers
179 views

why DFA to regex by two different methods differ

I was learning converting DFA to regex. I came across Arden's method which solve given DFA as follows: Ardens method Let us form the equations $q_1 = q_10 + q_30 + є$ $q_2 = q_11 + q_21 + q_31$ $...
2
votes
2answers
330 views

DFA of (aa+bb)(a+b)* + (a+b)*(aa+bb)?

Our class teacher gave us a descriptive definition of a language in a Quiz today and ask us to make its DFA. In the middle of quiz he also told us the Regular Expression(RE) of that language but we ...
9
votes
1answer
402 views

When is a regexp is not a Regular Expression?

Since I'm studying for my formal languages college course, I stumbled upon these fascinating posts (One Two) which describe how to find a prime number using a regexp. As I said, a regexp, not a ...
2
votes
1answer
352 views

Tokenization Problem

Yes, this is a quiz question. It's from a self-paced course, but the answer just isn't correct to me no matter how I look at it. There isn't really an active community to consult. My Regular ...
1
vote
1answer
72 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
0answers
48 views

Returning all the combinations of a string using regex

Is it possible for a regex pattern to return all the 2^n combinations of characters of a string as matches? For example, if the string is ...
4
votes
2answers
68 views

Does there exist a context-free language $L$ such that $L\cap L^2$ is not context-free?

I can see that $L$ has to be context-free but not regular here as regular languages are closed under concatenation and intersection. But $L\cap L^2$ looks too weird. I couldn't think of any $L$ that ...
3
votes
2answers
78 views

Regular expression for binary words with 1 in the middle

Given the alphabet $\{0,1\}$, generate a regular expression with the following language: $$ \{w\in \Sigma^* \mid w \text{ has odd length and its middle symbol is }1\}. $$ I'm having trouble finding a ...
1
vote
2answers
107 views

Is the language of words that contain a square regular or context-free? [duplicate]

$ L = \{w \in\{a,b\}^{*} : \exists_{x,y,z} , w=xyyz \wedge y \neq \epsilon \}$ I have a problem with this exercise. I need to determine if this language is regular, context-free or not both and ...
0
votes
1answer
41 views

$ L = \{xyyz\in\{0,1,2\}^{*} : y \neq \epsilon \wedge \exists_{a \in \{0,1,2\}} |y|_a \equiv 0 \}$

$ L = \{xyyz\in\{0,1,2\}^{*} : y \neq \epsilon \wedge \exists_{a \in \{0,1,2\}} |y|_a \equiv 0 \}$ I think this languages is regular. I write regular expression: $(1 + 2 + 0) ^ {*} (11 + ...
2
votes
1answer
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, ...
1
vote
1answer
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 ...
1
vote
1answer
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: ...
1
vote
1answer
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 ...
1
vote
1answer
40 views

How to prove that $\{\$x\$\}$ is a regular language if $x$ is derived from $L=\{w\}$ by substituting substrings?

Prove that if $L$ is regular over $\Sigma=\{0,1,2\}$ then the following language over $\{0,1,2,\$\}$ is also regular: $$ G=\{\$x\$|\exists w\in L: x\text{ is derived from }w\text{ by substituting } ...
1
vote
1answer
39 views

Is this context-free grammar correct for this regular expression?

I have created a context-free grammar $$ \begin{align*} &S \to S_1 \mid S_2 \\ &S_1 \to aS_3bS_4 \mid \epsilon \\ &S_2 \to bS_4 \\ &S_3 \to aS_3 \mid \epsilon \\ &S_4 \to aS_4 \...
1
vote
2answers
41 views

Does this DFA describe this regular expression?

For the expression (ab)*ba I came up with the following (very poorly drawn): However, this was not the correct answer - apparently the solution requires five ...
0
votes
1answer
194 views

Regular expression or automata for language with odd number of 0's and odd number of 1's

Let $\Sigma=\{0,1\}$ and $L=\{u \in \Sigma^* : u \text{ has odd number of 0's and odd number of 1's}\}$. How can I build a regular expression or an automaton for this language? I have no idea, and I ...
3
votes
1answer
78 views

Regular expression for words containing single 1 and even number of 0s

What would be a regular expression for the language of words containing a single 1 and an even number of 0s?
5
votes
3answers
1k views

Why is the number of states for DFA is 3n + 1 for this language

I'm taking online compilers course. It's long ended, so it wouldn't be cheating to ask a question on quiz here. Let $S_i$ be the string consisting of $i$ 0's followed by $2i$ 1's. Define the language ...
0
votes
0answers
15 views

What are some differences between regex (FSM) in computer science with regex in programming? [duplicate]

Computer science has automata theory with lessons on regular expressions and FSM. How are these different from regex engines used in programming such as C++, Perl, PHP etc.? I would like to know some ...
1
vote
2answers
57 views

Regular expression for words where the same symbol can repeat at most two times consecutively?

Having the alphabet $\{a, b\}$, how can I generate a regular expression for the language that does not have substring of three or more consecutive same symbol? For example, I can't have ${baaab}$ nor ...
-3
votes
2answers
374 views

DFA accept 00 as a substring

How can design this question if we have an equation like that ={wxw | w={0,1}* , x=00} accept 00 it means not contain 000,001,100, but accept all these {00,1001,110011,001000001.....}. Thank you for ...
3
votes
3answers
161 views

If $L$ is a regular language, then $s(L)$ is also regular

...where $s$ is a substitution that replaces each symbol of each string in $L$ with a regular expression. For example, if $L=a^*b$ and $s(a) =ab, s(b) = b^*$, we have $s(L) = (ab)^*b^*$. My ...
0
votes
0answers
59 views

How use generalized suffix tree to match prefix string?

I know that generalized suffix tree can match substring for a given pattern. But I have need a data structure which is able to match prefix of many strings. match sub string of of many strings. For ...
1
vote
1answer
45 views

Finding a correct regex for the strings with at least two $0s$

I am learning CFGs and before that I've made a RE (Regular Expression) for the language of "all strings with at least two $0$'s over the alphabet $\Sigma = \{0,1\}$." I made this: $(0+1)^*0(0+1)^*0(0+...
0
votes
0answers
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 ...
7
votes
4answers
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:/...
1
vote
1answer
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 ...
1
vote
3answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
2answers
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” ...
1
vote
1answer
54 views

Determining initial and final states from FA diagram

I am new to automata. And learning to find concatenation of two FAs. But this one has confused me I know how to do concatenation but I am confused that in FA 1, what does x1 means? Is it mean final ...
0
votes
1answer
51 views

regex - difference between $\Lambda+(a+b)^*b$ and $(b+aa^*b)^*$

$r_1=\Lambda+(a+b)^*b$ $r_2=(b+aa^*b)^*$ $r_3=b+\$+aa^*b+(b+\$+aa^*b)(b+aa^*b)^*(b+\$+aa^*b)$ For this FA, which i think of as accepting "$\Lambda$ or anything ending in $b$", i came up with $r_1$, ...
0
votes
1answer
49 views

Can someone explain the language L = {w: w = uu, u \in La(1*01*)}

I need help understanding the language L above. These are my understanding: - w = uu is a concatenation of ...
1
vote
0answers
65 views

Extending Thompson's NFA algorithm with backreferences

I'm looking for an algorithm as efficient as possible for a regex engine that supports submatch tracking (a.k.a capturing parentheses) and backreferences. What I mean by as efficient as possible is ...
1
vote
1answer
39 views

In which environment we use NFA(Non Deterministic Finite Automata)?

We have two types of Automata. One is NFA and second is DFA. These are little bit different but thing is that in which environment we prefer NFA over the DFA?
2
votes
1answer
135 views

Why does the concatenation operation imply the empty string?

I'm a noob reading Michael Sipser's Introduction to the Theory of Computation, and I'm at a part where he's demonstrating how to construct finite automata that accept languages described by regular ...
10
votes
3answers
2k views

Why is there no permutation in Regexes? (Even if regular languages seem to be able to do this)

The Problem There is no easy way to get a permutation with a regex. Permutation: Getting a word $$w=x_1…x_n$$ ("aabc") to another order, without changing number or kind of letters. Regex: Regular ...
0
votes
0answers
27 views

Example of a language with linear NFA, but exponential DFA [duplicate]

So I read that regex engines use NFAs instead of DFA because f size blowup for dfas. I want to get an example of a language for which the minimum DFA has an exponential number of states but it,s NFA ...
0
votes
2answers
56 views

Formal algorithm to test whether two given regular expressions define equal/identical or unequal languages

I'm trying to create a formal algorithm in order to determine whether two given regular expressions $a$, $a'$ define identical/equal or unequal languages and if those languages are subsets of each ...
1
vote
0answers
152 views

How to design a LL(1) grammar for basic regular expression?

I try to design a LL(1) grammar to parse the basic regular expression. Here's the origin grammar.(\| is the escape character, since | is a special character in grammar's pattern). ...
1
vote
2answers
64 views

Prove or disprove L is regular

There is question in one of my exercise but I couldn't prove or disprove anything about it. This is language $L$ which is introduced with grammar: $$S \to 0S1 | 1S0 | AA$$ $$A \to 0A | \lambda|A1$$ ...