Questions tagged [regular-expressions]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
391 views

Regex for divisibility by 123 in binary strings

Is there a regex that checks for divisibility by 123 in binary strings? This question can be found in the Algorithms’ textbook by Sedgewick and Wayne official website (question 7b in the Creative ...
2
votes
1answer
77 views

Is there a way to find a simple regular expression for this language?

Let $\Sigma$ be 0,1,2. I am interested in the language of all strings $w$ such that the sum of $w$ characters (where the char 0 is treated as the number 0, the char 1 as the number 1 etc) is ...
0
votes
1answer
49 views

Show that the regular language is contained in another

Let L1 and L2 be two non empty regular language. How can I show that the following expression is correct with an example ? $\bigotimes$ denote the transducer cross product. $L_1^+ \bigotimes L_2^+$ ...
0
votes
0answers
137 views

Operations on regular languages

I am taking a course on natural language processing that assumes the students have some background on theory of computation. I dont, but have read up till chapter 3 of the book "Speech and Language ...
0
votes
2answers
369 views

Regular expression for string with substring 010 and ending with 01

How can one design a regular expression for given string in title ? Also how can we draw DFA of that regular expression? I've tried many expressions but couldn't succeed, please help.
1
vote
1answer
85 views

Thompson Regular Expression Search Algorithm 3rd Stage

My professor assigned us to read Thompson' Regular Expression Search Algorithm paper. I am struggling to understand the third stage of the compiler. The first two stages are as follows: Check that ...
0
votes
1answer
286 views

Do all Regular Expressions describe Regular Languages?

I understand that for every regular language, there exists an equivalent regular expression. However, can that be used in the opposite direction? Does every regular expression have an equivalent ...
4
votes
1answer
476 views

Cartesian product of regular expressions?

My textbook has a problem to find the regular expression that describes the set of all strings of 0's and 1's whose number of <...
1
vote
1answer
295 views

Finding the regular expression equivalent for the given finite automaton

This is another homework problem I'm stuck with. For the given finite automata, I am asked to find out the equivalent regular expression. On inspecting the given automata, I started deducing the ...
1
vote
1answer
360 views

How do you convert a regular expression to its disjunctive normal form?

A regular expression $r$ is said to be in disjunctive normal form if it can be written in the form $r = r_1 +r_2 +\dots+r_n$ for some $n ≥ 1$, where none of the regular expressions $r_1, r_2, \dots, ...
0
votes
0answers
55 views

Can't tell whether the following language is regular or not: [duplicate]

I have to decide if the following language is regular or not. I suspect it is not regular, so I try using pumping lemma to prove it, but something goes wrong. Any help on how to use pumping lemma on ...
2
votes
2answers
316 views

Is there any algorithm which takes regular expression as input and finds if the regular language which expression describes is infinite? [duplicate]

Is there any algorithm which takes regular expression as input and finds if the regular language which expression describes is infinite?Does it have to do with pumping lemma? Additionally,is there an ...
2
votes
1answer
50 views

Can three regular languages be concatenated?

I can't seem to find anything about this and I wonder if I'm asking a silly question. If you have three languages $L_1=\{a,b\}, L_2=\{c,d\}, L_3 =\{e,f\}$, can they be concatenated? If yes, would ...
1
vote
1answer
28 views

DFAs that must reach a certain state at least once

I was given this question: Let M = (Q,Σ, δ, q0, F) be a deterministic finite automaton. Assume that r∈Q is a state of M that is different from the start state q0. Define the language A⊆Σ* to ...
-1
votes
1answer
98 views

Counter-example to regular expression statement

Show a counter-example to disprove the following statement: If $R1$ and $R2$ are two regular expressions, then $L((R1 \cup R2)^*) = L(R1^* \cup R2^*)$.
-1
votes
1answer
46 views

Regular Expression Building

I'm having trouble constructing a regular expression to meet the following criteria: $$\sum = \{0,1\}$$ $$\epsilon \in L$$ $$0 \in L$$ $$1 \in L$$ $$\forall x \in L, 110x \in L \land x01 \in L$$ ...
0
votes
0answers
139 views

Tool for NFA/DFA manipulation

I am look for a tool with any or all of the following features: Regular Expresstion to NFA converter that represents transitions as Binary Decision Diagrams NFA to DFA converter NFA minimization NFA ...
1
vote
1answer
429 views

Unambiguous grammar for regular expressions

How to define a non ambiguous grammar for regular expressions on the $\Sigma = \{a,b\}$ alphabet? Given that: If $\Theta = \{+, ^*, (,),\cdot, \emptyset\}$ is a set of symbols A regular expression ...
0
votes
0answers
222 views

Generating finite automata from regular expression [duplicate]

Right now I am trying to learn how to work with automata and regular grammar, and I encountered the following exercise: $(1^*01)11$ I found the following solution, but I am not really sure if it's ...
4
votes
3answers
4k views

Write a regular expression - Contains an equal number of 01 and 10 subtrings

I'm trying to write a regular expression for the language $L\subseteq\{0,1\}^*$ of strings that begin with $0$ and contain an equal number of occurrences of the substrings $01$ and $10$. ...
1
vote
1answer
852 views

How to transform Nondeterministic finite automaton (NFA) to regular expression equivalent

Im struggling to understand how to transform Nondeterministic finite automaton (NFA) of the following form: To a regular expression equivalent. What I have tried was using arden's rule. However I ...
1
vote
1answer
197 views

Difference between NFA and NBA

NFA (nondeterministic finite automata) accepts only finite words while a NBA (nondeterministic Büchi automata) accepts infinite words (and hence $\omega-$regular languages). I think the example ...
0
votes
1answer
1k views

Regular expression for the language containing neither aa nor bb

I want to create a regular expression for the language $L=\{ w \in \{a,b\} |$ w has neither aa nor bb as a subword$\}$. I've tried various things, but I can't seem to get the correct regular ...
3
votes
1answer
812 views

Minimum number of states in dfa accepting binary number with decimal equivalent divisible by $n$

I was aware of the fact that, if DFA needs to accept binary string with its decimal equivalent divisible by $n$, then it can have minimum $n$ states. However recently came across following text: ...
1
vote
1answer
298 views

Whether equivalence of different types of automata is of P-type?

I came across following problem: Which of the following problems is/are P-problems? (I) Equivalence of DFA's (II) Equivalence of NFA (III) Equivalence of regular expressions Now I know I ...
0
votes
1answer
31 views

How do you get a regex from this DFA? [duplicate]

I've been trying for hours. I'm teaching myself automata theory right now and I have this DFA: And I'm trying to create a regex from it by removing q1 first and then q2. I already managed to remove ...
0
votes
1answer
95 views

Prove this language is non-regular [duplicate]

I'm struggling to understand this question using pumping lemma to prove a language is not regular. Any help would be appreciated. Prove using the Pumping Lemma that the following language is not ...
0
votes
1answer
46 views

Semantics of Regex with boundary matchers

The regex /^(abc)$/ matches abc but why not abcdabc, ...
0
votes
0answers
62 views

Empty words in regular languages

Let $L_1,L_2$ be any $\Sigma$-Languages, with $l_1\in L_1, l_2\in L_2$ If I have a regular Language $L(l_1(l_2l_1)^*l_2)$ would the word $\omega=l_2$ be recognized? I'm confused because if $\epsilon \...
1
vote
1answer
60 views

How to find a regular expression

I know how to find a regular expression when given a FA. But how do I find a regular expression given just a language and its rules? For example, for the language $L \subset \{ a,b\}^* $ which ...
0
votes
1answer
233 views

How to build a parser for syntactic analysis of regular expressions?

Is it possible to build a parsing algorithm that build a parse tree using a top-down method that simulate a derivation process for regular expressions, like we do for type 2 languages? My guess ...
0
votes
1answer
49 views

Do we need regular expression first or finite state automata in lexical anlysing? [closed]

I'm a bit confused about the concept of finite state automata (FSA) and regular expression (RE) in lexical analysis. I have reading some books about compiler construction. At the part of tokenization, ...
1
vote
2answers
445 views

Is the difference between two regular expressions a new regular expression?

Let say the following: Given Ax and Bx two literals which represent POSIX regular ...
5
votes
1answer
289 views

Why are regular expression quantifiers greedy by default?

I can't count the number of times I've seen questions on StackOverflow related to regular expressions where the problem was due to the programmer not understanding the impact of greedy quantifiers. ...
7
votes
1answer
579 views

Can we convert an NFA to a regular expression of polynomial length?

Can we convert an NFA having $n$ states to a regular expression of length $\mathrm{poly}(n)$? In contrast, it is well known that a regular expression of length $n$ can be easily converted to an $\...
2
votes
2answers
615 views

Regular expression for even/odd string on alphabet

Given the alphabet $\{ a,b \}$, if I want to build the regular expression for even/odd lenght strings, I can think that an even lenght string is given by some combination of $a$'s and $b$'s, and the ...
0
votes
0answers
51 views

Recurrence relation for a star and a dot wildchar pattern

. Matches any single character, * Matches any sequence of characters (including the empty sequence). dict = ["cat", "cats", "...
0
votes
1answer
106 views

What is the deterministic finitite automaton (DFA) for the regex “.*b.”

I'm looking for a finite state machine that can match inputs to the regular expression .*b. deterministically (i.e. it cannot change state w/o being fed input and ...
1
vote
1answer
65 views

Giving a regular expression for a situation of a question

I have the following question regarding a situation given and we are then required to derive a regular expression out of it. What i have to do now i to give a regular expression for this language ...
0
votes
2answers
122 views

Are these two regular expressions equivalent?

$u^*v(w \cup xu^*w)^*$ and $u^*v(w \cup x(u)^*w)^*$ Is that extra set of parentheses around the second $u$ needed?
-1
votes
1answer
47 views

Create DFA with String of {a,b} [duplicate]

I Want to Create Regular Expression from string of {a,b} that it contains neither the substring ab NOR ba?How I can do it?
2
votes
1answer
348 views

Show that $L = \{1^n w 1^n | n > 0 \text{ and } w ∈ \{0,1\}^*\}$ is regular

Show that the following language $L$ is regular by describing it using a regular expression. $$L = \{1^n w 1^n \mid n > 0 \text{ and }w ∈ \{0,1\}^*\} $$ My (apparently incorrect) answer: Given ...
2
votes
1answer
92 views

Creating regular expression with sub sequences of strings

I am creating a program which searches for particular types of strings. The alphabet of these strings are in $\{a, b, c\}$, for which every sub string of length 3 contains exactly $c$. Some strings ...
3
votes
2answers
81 views

Proving OP(L) is regular [closed]

I did some searching before I decided to ask this question and there was nothing similar to my question that helped me. So I came to CS stack-exchange for hints. So, I am currently working on a proof ...
0
votes
2answers
335 views

Regular expression $(a^{*}b^{*})^{*} = \left( a+b \right)^{*}$ proof

Im having a lot of trouble proving that for the Regular expression $R_{1} = \left( a^{*} b^{*} \right)^{*}$ and $R_{2} = \left( a+b \right)^{*}$ that $L \left( R_{1} \right) = L \left( R_{2} \right)$. ...
0
votes
0answers
135 views

Simplification of regular expressions

$(0+1)^*.1.(0+1) + (0+1)^*.1.(0+1)$ and $(((0^*.1^*)+1)^*(0+1)^*)^*$ I have studied Arden's theorem $R=Q+RP$ has a unique solution $R=QP^*$ and some identities like $E+RR=R$ and $E.R=R$. I have ...
0
votes
2answers
162 views

Is $L=\left \{ wxw \,\,|\,\,w,x \,\in \left ( a+b \right )^{+}\right \}$ Regular? [duplicate]

Question Is $L=\left \{ wxw \,\,|\,\,w,x \,\in \left ( a+b \right )^{+}\right \}$ regular? My Understanding/Doubt We can say that Language $L_{2}=\left \{ wxw \,\,|\,\,w,x \,\in \left ( a+b \...
2
votes
1answer
75 views

What language can be created from a regular expression with nulls?

The usual regular expressions I have seen are those with non-null inputs (e.g. $a$, $b$). A few days ago, I saw, for the first time, a regular expression that has a null ($∅$) in it. $$ r_{1}= (cε + ...
1
vote
1answer
466 views

Regular Expression converted to NFA

Hello, all, First time poster, here. Anyways, here is my question from the textbook Introduction to the Theory of Computation, 2nd Ed. (Sipser, 2006). Question 1.19 is asking us to convert a regular ...
1
vote
2answers
1k views

Regular expression with out the substring bab or abb?

I'm having a problem coming up with a regular expression for a language L = {a,b} with out the substring bab or abb? I can come up with the one for just one substring, like a*(b* aaa* )* b* a* to ...