Questions tagged [regular-expressions]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
13 views

Build a regular expression that specifies the language L in the alphabet Σ = {a, b, c}:

Build a regular expression that specifies the language L in the alphabet Σ = {a, b, c}: L = {w : w does not contain aaab}. For this task, you also need to build a deterministic finite automaton, but I ...
user avatar
-1 votes
0 answers
22 views

Automata Regular Expression that remembers n iterations

Given is $L = \{\sigma_1 ~u~\sigma_2~v~\sigma_3 ~|~ \sigma_{1,2,3} \in \Sigma,~~ u,v\in \Sigma^*,~ |u|=|v|,~ \sigma_2=\sigma_3 ~or~ \sigma_2=\sigma_3 ~~\mathbb{but ~~ not ~~ both} \}$ I do not ...
user avatar
  • 654
0 votes
0 answers
60 views

Prove $ L' = \{uv \mid u,v \in \Sigma^*,\ vu \in L\}$ is a regular language where $L$ is regular [duplicate]

Let $L$ be a regular language with alphabet $ \Sigma $. Prove that the language $$ L' = \{uv \mid u,v \in \Sigma^*,\ vu \in L\} $$ is regular.
user avatar
1 vote
0 answers
29 views

Finding equivalence class for $R_L$ of a regular language

Let $\Sigma = \{ a, b, c\}$, $$ L = \{w\in\Sigma^*\mid w \text{ starts with $ab$ and ends with $ab$}\}, $$ i.e. $L = ab(\varepsilon + (a+b)^*ab)=ab+ab(a+b)^*ab$. I need to find a regular expression ...
user avatar
0 votes
1 answer
38 views

Prove that $L=\{a^n b^l : n \leq l\}$ is not regular by pumping lemma

I'm currently trying to prove that $L=\{a^n b^l : n \leq l\}$ is not regular by pumping lemma My proof: If we choose $w$ such that $w=a^P b^P$, then since $|xy| \leq p$, $y$ must be $a^P$, meaning it ...
user avatar
  • 111
0 votes
1 answer
58 views

Regular Expression - binary digits, no occurrences of 111, solving methodology?

Can someone show in some simple steps how one goes about creating a regular expression from binary digits that excludes all occurrences of 111? What I am having trouble is how one starts these sorts ...
user avatar
0 votes
1 answer
49 views

creating regular expressions from given language

The first question is $L_1 = \{w \in \{a,b,c\}^∗ \mid \text{$w$ ends with $ca$}\}$ I started by creating a DFA for that for better understanding and then making a regular expression. and the regular ...
user avatar
0 votes
1 answer
39 views

Finding the equivalent regex for a formal grammar

We have the following formal grammar: $a, b$ are terminal symbols. $S, A, B$ are non-terminal symbols. $S$ is the startsymbol. Thinking in terms of a nondeterministic finite automata $q0$ indicates ...
user avatar
1 vote
1 answer
24 views

Regular Expression for binary string that contains number of zeros not a multiple of 3

I want to generate a regular expression by using only + (or, union), * (0 or more), and (^+ 1 or more) operations. The language contains only 0 and 1. The problem is to generate a regular expression ...
user avatar
1 vote
1 answer
32 views

Solution Verification: Regular expression that starts with $a$ and doesn't contain $aba$ pattern.

Write a regular expression that starts with $a$ and doesn't contain $aba$ pattern. My Solution: If my expression doesn't contain $aba$, then it must not have a $b$ alone in the middle of it before ...
user avatar
  • 2,029
1 vote
2 answers
36 views

Constructing grammar for $a^ib^j$ / $i\neq j$

I want to construct a grammar for the following regular expression: $a^ib^j / i \neq j$. I did it the following way: $S_1 \rightarrow aaSb | aaAb$ $A \rightarrow aA | \epsilon$ $S_2 \rightarrow aSbb | ...
user avatar
1 vote
1 answer
122 views

a^m b^n c^n prove it's not regular/pumping lemma

How to prove that $L = \{a^mb^nc^n \mid n, m \geq 0\}$ is not regular by the pumping lemma My attempt: Let's suppose $L$ is regular. There exists a pumping constant p, and we choose $w = a^pb^pc^p$ ...
user avatar
0 votes
3 answers
96 views

$a^nb^n$ language vs $a^nb^m$

I always read that $\{a^nb^n \mid n>0\}$ is not a regular language because automata doesn't have memory, while $\{a^nb^m \mid n, m>0\}$ is regular because we don't have to remember anything ...
user avatar
1 vote
1 answer
29 views

DFA conversion through state elimination and arden's method

I have tried to convert the following DFA to regular expressions through two different methods: Arden's method, and state elimination one. I have arrived to two different regular expressions: Arden's ...
user avatar
0 votes
1 answer
37 views

intersection of two regular expressions [closed]

If we have two regular expressions $L_1 = aba^*b^*c^*$ and $L_2 = a^*b^*c^*ab$, how do we get $L_1 \cap L_2$ get? I found the answer to be $L_1 \cap L_2 = ab + abab$ But I don't know how it was ...
user avatar
1 vote
1 answer
28 views

Write a regular expression over the given language. [closed]

This question is really really tough for me. It asks to write a regular expression for the following language (with the given alphabet of $\{a,b\}$: $$L=\{w:w\text{ has even length and has an odd ...
user avatar
1 vote
1 answer
37 views

How to write a regular expression for the given language?

This question wants me to write a regular expression over the following language: L = {w | w has exactly two a's and at least three b's} (and the alphabet is {a,b}) I have dealt with this by drawing ...
user avatar
2 votes
2 answers
119 views

Regularity of a language checker

I have to check if this language is regular or not:$$L = \{w(bb)^nw^R:w\in\{a,b\}^* \land n \in \mathbb{N}\}$$ My thoughts are if this language is regular so the RE for this is: $(bb)^*$ where $w$ and ...
user avatar
0 votes
0 answers
61 views

is {w in {0,1}* | #0(w) = #1(w)} a regular language?

is L = {w in {0,1}* | #0(w) = #1(w)} a regular language? I've managed to prove it is context free, but this doesn't really help. I've also saw a hint (here - prove that l={w ∈ {0, 1}*: n0(w) ≠ n1(w)} ...
user avatar
1 vote
1 answer
109 views

Regular expression for a language string

I'm trying to build a regular expression for this language: $$L=\{w\in\{0,1\}^*: \text{at least two} \ 0's \ \text{and at most two} \ 1's\}$$ So, it's mean that this language has $|w|_0 \geq2$ and $|w|...
user avatar
0 votes
0 answers
17 views

Is every regular expression corresponding to a superpolynomial acyclic minimal DFA always superpolynomial?

In this question, we consider the relationship between large deterministic finite automata and their corresponding regular expressions. All automata in this question, including under logical ...
user avatar
  • 1,485
1 vote
1 answer
25 views

Using complement to create a DFA with a specific condition

In my understanding, the complement of an automaton is when the final states become non-final and the non-final states become final. I tried to apply this method to create an automaton that never ...
user avatar
0 votes
1 answer
37 views

Regular Expressions and intersection.

The exercise: $L_1 = L(E_1)$, where $E_1$ is the regular expression $(11)^* (00)^*$. $L_2 = L(E_2)$ where $E_2$ is the regular expression $(111)^* + (111)^* 0(00)^*$. $L_3 = L(G)$ where $G$ is the ...
user avatar
0 votes
0 answers
29 views

what is the most recommended book to learn automata and formal languages?

could you recommend a book to learn automata and formal languages? It is my first course in this subject and I would like a good bibliography with exercises and demonstrations. In particular I would ...
user avatar
  • 151
0 votes
1 answer
58 views

If $𝐿$ is regular, will $L' = \{v\in L:\,\exists w\in L: w = v^R\}$ be regular also?

Let $L$ be any language over $\Sigma = \{a, b\}$. Using $L$, we define a new language $L$ which includes every string $w$ if both $w$ and its reverse $w^R$ are in $L$. Show that $L'$ is regular ...
user avatar
1 vote
1 answer
74 views

Context Free Grammar for strings of $z^n$y$x^m$ $w^n$

I am trying to make a context-free grammar that generates all the strings in the language: $\{z^nyx^mw^n : m,n \ge 0\}$. Right now for my rules I have: $S\to yX$ $S\to y$ $X\to e$ $X\to xX$ $S\to zXSw$...
user avatar
2 votes
2 answers
544 views

How to write a regular expression for every string w over {0,1} where w is a binary string with value of at least 40.

So far I have realized that minimum value is 101000 in binary, but we also have to accept strings like 110000 and ...
user avatar
0 votes
1 answer
27 views

regular expression and equivalent right linear grammar

I have some question regarding regular expressions and right linear grammer. I know that for any regular expression there is an equivalent right linear grammer. Is that sentence is right also for ...
user avatar
  • 33
0 votes
1 answer
68 views

Regular expression for language recognized by NFA?

I am trying to find the regular expression for the language recognized by the following NFA: $$K=\{1,2,3\},$$ $$\Sigma=\{x,y,z\},$$ $$s(\text{initial state}) = 3,$$ $$F(\text{final state}) = \{1\}.$$ ...
user avatar
-1 votes
2 answers
86 views

Expressing absolute value intervals in terms of inequalities

The question below is in my textbook about ınequalities of absolute values. The question Express the interval in terms of an inequality involving absolute value. is ...
user avatar
0 votes
1 answer
37 views

Trying to simplify a regular expression of which I currently have an abominably long one

I have a pretty simple question, but I don't know how to simplify this regular expression further from the answer that I have. I'd like to find a regular expression for the set of strings over ...
user avatar
5 votes
2 answers
74 views

Function from natural to lexicographically ordered words of a-z

I think I am looking for a very basic lexicographic ordering concept/function/algorithm, but I'm stumped. Basically, it has to produce the following mapping: ...
user avatar
1 vote
1 answer
107 views

Simplify $R:=0^*+0^*1\left(1+000^*1\right)^*0^*$

I'm trying to simplify the following REGEX: $$R:=0^*+0^*1\left(1+000^*1\right)^*0^*$$ $R$ is the result of transforming a GNFA that recognizes $L:= \{w \in \{0,1\}^* | \left(\forall \ i \in \left[1,|w|...
user avatar
0 votes
0 answers
68 views

Design a regular expression that accepts the language of all binary strings with no occurrences of bab [duplicate]

i have tried a∗b∗ ∪ b∗a∗ ∪ a∗b∗aa+b∗a∗ , it can be represented as abbaaaba which meets the requirement. However, I am not very confident in my answer and want to ask if anyone can help confirm this ...
user avatar
  • 21
0 votes
0 answers
125 views

Give the regular expression for the set of strings $\{a, b, c\}$ that do not contain substring $aa$

Give the regular expression for the set of strings $\{a, b, c\}$ that do not contain substring $aa$. How to solve this regular expression? I've been thinking for a long time to generalize that. But ...
user avatar
1 vote
2 answers
169 views

Does there exist a set of strings $L \subseteq 1^*$ such that $L$ is an irregular language?

I am currently trying to prove/disprove the following statement from my textbook: Let $1^*$ be the regular language of all strings consisting of only ones. Does there exist a set of strings $L \...
user avatar
1 vote
1 answer
83 views

Is the Kleene Star $*$ distributive over concatenation?

I'm currently learning about automata theory and I came across the following question: Given an arbitrary set $L$ of symbols. Is $(L \: \cdot \: L)$* = $L$* $\cdot$ $L$* true, where * refers to the ...
user avatar
  • 417
1 vote
2 answers
490 views

What is the regular expression representing all binary strings where no occurrence of 00 is immediately followed by a 1?

I am currently working on constructing regular expressions that match a description of a given set of strings from practice problems in my textbook (no solutions are provided in it). I am trying to ...
user avatar
1 vote
2 answers
43 views

Does the Kleene Star allow for n-time concatenation or infinite concatenation of a word with itself?

When describing the Kleene Star, is the following correct: The Kleene Star applied to a word w allows for the word to be concatenated with itself 0 to n times, with n [element] N. where N is the set ...
user avatar
1 vote
1 answer
46 views

NFA of language $1^*(001^*)^*$

My textbook has a problem - Find NFA of language $1^*(001^*)^*$. I have following question- Suppose A is a language with regular expression $(001^*)^*$. Then will each occurrence of the expression ...
user avatar
  • 155
0 votes
1 answer
117 views

Is $L = \{xwyw^r \mid x,w,y \in (a+b)^+ \}$ regular?

$L = \{ xwyw^r \mid x,w,y \in (a+b)^+ \}$ where $w^r$ is the reverse string of $w$. If we take $w = {}$minimum string possible ${} = a$ or $b,$ I think it could be regular Lets say $w=a$, then RE ...
user avatar
  • 67
1 vote
0 answers
107 views

convert from dfa to regex

I was asked to form this automata to a regular expresssion : so far im stuck at this stage : can somepne help me please ?
user avatar
1 vote
0 answers
797 views

Regular expression for {$w:w$ starts with $0$ and has odd length, or starts with $1$ and has even length}

Problem in my textbook. Give a regular expression for the language {$w:w$ starts with $0$ and has odd length, or starts with $1$ and has even length} alphabet is $\{0,1\}^*$ My answer: $(0\cup1(0\...
user avatar
  • 155
-1 votes
1 answer
39 views

Minimum length regular expression for $\{ w| w\in\{0,1\}^* $ and for every x that is a prefix of w, $|\#1(x)-\#0(x)| \leq2\}$

$L(M) = $ $\{ w| w\in\{0,1\}^* $ and for every x that is a prefix of w, $|\#1(x)-\#0(x)| \leq2\}$ I tried to use some online convertors and only found this regular expression: ((a+(ϵ+a(ab)*b+b(ba)*a)(...
user avatar
1 vote
1 answer
347 views

Showing star-freeness of recursively defined languages

Problem: Define a sequence of languages on $A$, a finite alphabet as $D_0 = 1$ (empty string) and $D_{n+1}= (aD_nb)^*$. Show that each $D_i$ is star-free (for each there is an equivalent star-free ...
user avatar
1 vote
0 answers
324 views

Regular expression generating language {$w: w$ contains at least three $1$s}

I am learning automata. As an answer to following question in my textbook, I came up with this answer. Give regular expression generating language {$w: w$ contains at least three $1$s} $0^*10^*10^*1(...
user avatar
  • 155
1 vote
1 answer
58 views

Is Shuffling of a regular language regular too?

If $A$ be regular language, How we can prove that $A^{'}$ is regular too? $A^{'} = \{a_{2}a_{1}a_{4}a_{3} ... a_{2n}a_{2n-1} \mid a_{1}a_{2}a_{3}...a_{2n} \in A\}$ Is there any way to prove that even/...
user avatar
  • 133
2 votes
0 answers
89 views

What is the easiest way to determine the list of all strings up to length N accepted by DFA or regular expression?

For example I have the next simple regular expression: (11|0)+ It is clear that size of the set of strings that match with this regular expression is infinite: <...
user avatar
  • 387
0 votes
1 answer
35 views

Creating a regex from regular language

I need to create a regex from this language: $L = \{w\sigma \mid w \in (\Sigma − \sigma)^*; \Sigma = \{a, b, c, d, e\} ; \sigma \in \Sigma\}$ but I don't understand the logic of this language. If $\...
user avatar
0 votes
1 answer
188 views

How to provide a regular grammar equivalent to context-free grammar?

I know that a regular grammar needs to be of the form: A -> a A -> aB, or A -> λ (lambda) But I am not sure of the steps needed to create a regular ...
user avatar

1
2 3 4 5
13