Questions tagged [regular-expressions]
Questions about regular expressions, a formalism to describe regular languages.
610
questions
0
votes
1answer
44 views
CFG-Infinite recursion
As you see, the string production process never ends.
Can someone explain me if this language is regular or not ?
$ S->ΑΒS $
$ A->S $
$ B->aBb $
2
votes
1answer
32 views
Pumping Lemma,regular languages
Lets say that we have the language L = { $a^n$$b^m$$c^{m+n}$ $|$ $m$,$n$ $>=0$ }
What is the way that i should follow to prove
that the language is not regular?
Assume that the language is ...
0
votes
1answer
29 views
validation of a pumping lemma proof for regular languages
I have the following regular expression:
Of course I could think of a word like $w=a^{m+2}b^{m+2}c^{2m+3}$ and continue with the proof BUT
I was just wondering, because $L$ is made up of a union of ...
0
votes
1answer
19 views
What is Pumping length for Union of Regular languages?
This is an exam question.
For E = {a,b}. let us consider the regular language
$L= \{x|x = a^{2+3k} or x=b^{10+12k}, k >= 0\}$
Which one of the following can be a pumping length (the constant ...
0
votes
0answers
23 views
I can't seem to convert a NFA to a regex. What am I doing wrong? [duplicate]
I have the following diagram :
I try to remove state 3:
Now I do this:
What do I do now to get my regular expression? I'm stuck.
4
votes
1answer
224 views
What is the computational complexity of “real-life” regular expressions?
Regular expressions in the sense as equivalent to regular (Chomsky type 3) languages know concatenation xy, alternation (x|y), ...
0
votes
1answer
17 views
Convert the given NFA to DFA
I am trying to find an DFA for the regular language given by the expression $L\left( aa^{\ast }\left( a+b\right) \right)$.
First simplifying $L\left( aa^{\ast }\left( a+b\right) \right)$ we get
$L\...
-1
votes
1answer
27 views
Turing Machine construction of M=wwRw form
Construct a Turing machine for
M = {wvw| v, w ∈ {a, b}*, reversal(v) = w}.
I tried to imagine that I will have to divide the string into 3 equal parts and check if ...
-2
votes
0answers
34 views
Regular Expression and Finite Automata for the language of Odd-Odd
Regular Expression and Finite Automata for the language of Odd-Odd i.e. all string should contain odd numbers of x’s and y’s but in any order, assume the ∑ = {x,y}. For Example: xy, xxyxyy, xyxyxy, ...
1
vote
1answer
20 views
Is regex with backreference still able to be implemented by finite automata?
I recently learned that regex support backreference which enables referring to a matched group in the pattern itself. E.g. a regex (.)\1{2,} matches two or more ...
-1
votes
1answer
18 views
How can I prove that the accepted language of a given DFA or NFA or REGEX is equivalent to a given language
I found this How do I verify that a DFA is equivalent to a NFA? but as it states it is not really a good question more of how can I check myself during an exam. Because as you might know to do this by ...
-3
votes
1answer
34 views
Construct regular expression for given language
How to construct regular expression for language L={a,b,c} which contain all words starts with bab and ends with babc?
0
votes
0answers
49 views
Does the order of ripping off the states matter?
Do we get same regular expressions at the end regardless of the order that we take the states step by step? Can somebody prove by exemplification?
3
votes
1answer
104 views
Why is this language a regular language?
Came across this in a book, and I'm wondering why the following language is regular?
$$ L = \{a^nww^R: n \geqslant 0, w \in \{a,b\}^3\}$$
Is it correct to say that $$ \{a^n : n \geqslant 0\} $$ is a ...
0
votes
2answers
39 views
Regular expression for a palindrome of finite length?
I have a language $$ L = \{ww^R, w \in \{ab\}^5\}$$
I know this is a regular language because it is finite (since w can only be of length 5). I want to prove it's a regular language, so I'd create a ...
1
vote
1answer
36 views
How to create a regular expression for this language?
I have a language:
$$ \{a^jb^k \mid j \neq k \text{ and } j \equiv k \pmod 3 \}$$
I want to prove that this language is regular. My first thought was to create a regular expression that accounts for ...
1
vote
1answer
54 views
RE Construction: Strings of even length in alphabet {a,b,c} that contain exactly one a
i am reviewing older exams from my computational theories lesson in university and i am struggling to figure this one out:
Construct a regular expression for the following language: Strings of even ...
26
votes
11answers
3k views
Unusual applications of regular expressions?
I am looking for some interesting applications of regular expressions.
Can you name any unusual, or unobvious, cases where regexes find their application?
1
vote
1answer
28 views
Construct regular expression that contains the substring
I need to write a regular expression for the following set of strings on Σ = {a, b, c} in which the number of b’s is even, and contains abcba as a substring.
So far, the even number of b's can be ...
0
votes
0answers
18 views
Construct a DFA with reduced states equivalent to 10 + (0 + 11)0*1
I have found this question in a book. I could convert it into its equivalent DFA. But the problem is with the "reduced state" part. I think the answer given in the book is wrong. What would be the DFA ...
0
votes
2answers
37 views
convert RE to NFA
The Regular Expression i am having trouble with is the following a(b|bcc*)*c. My main concern is what do i do with the c*? I can lay the rest of the diagram correctly (i think) but that part is ...
2
votes
2answers
36 views
Proving non-regular language using the pumping lemma
I would like to verify that the following language is not regular.
I know that if the pumping lemma is not valid then the language is not regular. (but its not enough to prove that the language is in ...
1
vote
2answers
104 views
Over the alphabet {a,b,c,d}, how would i construct a NFA that only accepts strings that end with a letter that is already part of the string?
I've been trying to create a NFA that accepts strings that end with a letter that exists in the string. For example abcdb, cbdd, acac etc. while strings like abc aacd etc are not accepted since the ...
-1
votes
2answers
60 views
Regular expression without 00 as a substring
I want to create a regular expression for the language:
$L=\{w \in \{0,1\}\mid w \text{ does not contain 00 as a substring}\}.$
I've tried various things, but I can't seem to get the correct regular ...
2
votes
3answers
110 views
An approach to determine whether language is regular or not?
I have the following problem. I need to determine whether this language is regular or not:
$L:= \{ w \in \Sigma^*: \forall \alpha ∈ \Sigma, |w|_\alpha \text{ is even or divisible by 3}\}$
$|w|_\...
0
votes
1answer
29 views
Is this a valid DFA for (a|b)*abb?
I'm trying to come up with an alternate DFA for accepting (a|b)*abb than the one present in the dragon book. Here's the one I tried:
It seems valid to me but I'm ...
0
votes
0answers
12 views
How to write regular expression [duplicate]
The set of all strings over {0,1} such that every block of 4 consecutive symbol contain at least two 0's
Can you guys tell me what is the correct answer for this ?
1
vote
0answers
13 views
Regex vs line by line read efficiency - general concept question
Say, I have a file that is somewhere between 10-20 pages long. I need to extract 10-20 pieces of information from it that I can fairly easily extract using a series of regex-es or by running code that ...
0
votes
0answers
43 views
Regular grammars
I am fairly new to automata, regular expressions and regular grammar. I am struggling to understand how to define the regular expression (abc)* into one or several regular grammar expressions.
...
0
votes
0answers
44 views
McNaughton-Yamada Algotihm (1960) Regular Expression to DFA without passing through NFA
I have a homework problem here. It asks me to use the McNaughton-Yamada algorithm to first convert a regular expression to a DFA, and then minimize this using a partition argument. I can do the latter....
3
votes
1answer
79 views
Arden's Rule, DFA & NFA to regular expressions
I have been trying to figure out the Arden's Rule and the equational method to transform DFA's & NFA's to RE. I know what the rule state:
if x = s + xr
then x = sr*, with $s,r\in$ Regular ...
1
vote
2answers
83 views
Prove the following language is regular?
Assume $L_1$ is a regular language, and define:
$$L = \{wcv ∈ \{a, b, c\}^* \mid |w|_a + 2|v|_b ≡ 3 \bmod 5, w, v ∈ L_1\}.$$
Show that $L$ is regular.
I first tried to prove by showing that the ...
1
vote
1answer
46 views
Are these REs equivalent?
I have to implement a compiler for a given language as part of an assignment.
The language is kept simple enough such that it can be fully expressed through REs.
My question lies with two of the REs ...
2
votes
2answers
61 views
regex of three repeating number
I need a regular expression, not one using coding syntax, to write an expression that has a vocabulary of 1,2,3 and every string in the language has at most one occurrence of the substring 222 but ...
0
votes
2answers
55 views
Generating regular expressions not containing abc
Let sigma = {a,b,c}. How do I generate a language L that does not containg abc?
Any guidance is appreciated!
1
vote
1answer
25 views
How to describe the languages of these regular expressions in plain English?
This is actually a question my lecturer gave us, so I know that it's kind of homework, but I tried to answer this and still had no luck.
The question is
Give English description of the languages ...
1
vote
1answer
62 views
Converting DFA to Regular Expression Using State Removal
I'm trying to convert the following NFA to a regular expression.
I've attached my work below and end up with the expression $aa^*bb^*$. As far as I can tell, this doesn't seem correct but I've been ...
0
votes
0answers
28 views
How to write a regular expression that excludes certain strings? [duplicate]
It's a homework problem.
Assume $\Sigma = \{a ,b\}$, I am asked to construct a regular expression that does not have both the substrings bba and abb.
My idea was: construct a regex that matches ...
1
vote
3answers
156 views
Large DFA to regex?
For an assignment for one of my courses, one of the questions is to provide a regular expression for the language:
"the set of strings such that the number of 0’s is divisible by six, and the number ...
0
votes
0answers
48 views
Prove the equivalence between regular expressions (cb*c+cb*b)* and (cc)*+(cc)*(cb)(b+c)*
I need to prove the equivalence of the following regular expressions:
(cb*c+cb*b)*
(cc)*+(cc)*(cb)(b+c)*
using the following equivalence rules:
• (1) (E + F) + G = E + (F + G)
• (2) E + F = F + E
...
-1
votes
2answers
131 views
Why L' is not regular?
$$L'=\{ww|w\in L\}$$
I need to give an example of regular language L for which the concatenation of 2's $w$ gives $L'$ which is not regular.
How can I give such an example if according to closure ...
1
vote
2answers
95 views
Prove that the language $\{a^ib^i | i\geq 0\}$ is not regular? (Do we just consider $a^nb^n$, where $n$ is the pumping length?
I think to prove that $\{a^ib^i | i\geq 0\}$ is not regular, we just have to consider the string $a^nb^n$ (which is in the language) and apply the pumping lemma. But I'm not sure how to proceed using ...
0
votes
0answers
101 views
Strings that do not contain 11 as a substring
Today I had a couple of formal language lectures. The Instructor wrote a regular expression for the alphabet $\{0,1\}$ which does not include any string which includes "11" as a substring.
She wrote ...
3
votes
1answer
39 views
Slowest growing upper bound for the minimum length of a complementary prefix regular expression
A postfix regular expression acting on a binary alphabet (specification from this post) can be described using the following grammar,
...
2
votes
4answers
70 views
How much more powerful are regexes in modern programming languages compared to regular expressions from the theory of computation?
Are the ones in modern programming languages equivalent to, say, Context-Free Grammars or is there an intermediate (between finite automata and CFGs) set of languages that it covers?
0
votes
1answer
15 views
How do I prove regular/non-regular with Nerode-Theorem? How to use it?
$L_{1}=\left\{w \in\{a, b\}^{*} | \#_{a}(w)=0\right\}$
$L_{2}=\left\{w \in\{0,1\}^{*} | w=u v u \text { with } u, v \in\{0,1\}^{*}\right\}$
I have problems to prove regularity with the nerode ...
1
vote
2answers
39 views
In an NFA that recognizes L(ab) where ab is a regular expression, what is the point of the empty string transition?
I'm reading Introduction to Computational Theory by Michael Sipser. He provides the NFA below as one that recognizes the language of the regular expression $ab$.
What is the purpose of the middle two ...
1
vote
1answer
69 views
How specifically do I need to describe (in words) the language of a regular expression?
For the regular expression $(a^*ba^*b)^*a^*$, I want to learn how to describe it in words. I know there are an even number of $b$s but how much do I need to explain it? Do I need to explain it enough ...
0
votes
0answers
46 views
Why is a Context Free Grammar that is simultaneously in Chomsky Normal Form and Greibach Normal Form regular?
In my course materials, there is one sentence about how if CFG is in Chomsky Normal Form, it is not regular, and if it is in Greibach Normal form, it also is not. But when a grammar is simultaneously ...
1
vote
1answer
34 views
Algorithm to generate inputs with certain properties, but not accepted by a given regular language
General
Given a regular language $L \subset \Sigma^\star$, I wish to generate at least one string not in $L$. (Obviously, this requires that there exists such a string; i.e., that $L \neq \Sigma^\...
