Questions tagged [regular-expressions]
Questions about regular expressions, a formalism to describe regular languages.
642
questions
0
votes
0answers
16 views
Check if the regular expression r made up of the single symbol alphabet Σ = {a} defines language L(r) = a* [duplicate]
I have got to write an algorithm programatically using haskell. The program takes a regular expression $r$ made up of the unary alphabet $ \Sigma = \{ a \} $ and check if the regular expression $r$ ...
1
vote
3answers
52 views
Regular Expression for language [duplicate]
I have a grammer with the following productions,
S -> aA | bC | b
A -> aS | bB
B -> aC | bA | a
C -> aB | bS
I have to construct regular expression for ...
0
votes
1answer
57 views
Conversion of RE to NFA
I've a question regarding this diagram. I'm thinking of adding a new state between q5 and q6 that accepts a lambda value but I'm not quite sure or this diagram is correct?
And in what situation we add ...
0
votes
2answers
85 views
Find language and regular expression
I don't know how to find the Language and the regular expression for each one.
there are any special method for those kind of question?
0
votes
2answers
108 views
How do you read the regular expression (0^∗10^+)^+?
Give an example of a string in the language of $(0^*10^+)^+$.
I've been asked to give an example of a string in this language but I'm confused on how to read this notation. I'm guessing the ...
0
votes
1answer
54 views
Create an optimal to express all natural number as an arithmetic expression using the alphabet $\Sigma=\{(,),1,+,\times\}$
Hope you had a fantastic christmas break :)
I am trying to find an algorithm in polynomial time that finds the shortest arithmetical expression (the one with the least amount of 1 symbols) to express ...
2
votes
1answer
60 views
Context Free Grammar to Regular Expression?
I want to learn whether I can create regular expressions from the given Context Free Grammar. I found some examples that can be translated to regular expressions. However, all of them were like this: &...
0
votes
1answer
31 views
If L is context free and R is regular then R – L must be context free?
Hi I am wondering if L is a CFL and R is RL then would the difference R - L be a context free language?
The difference might be the CF part of the language left then it would be, but I'm not sure how ...
-1
votes
1answer
24 views
Prove that the class of regular languages is closed under the Kleene + operation. That is, show that if L is regular, then so is $L^{+}$
This is my attempt at a proof:
Let $E$ be a $REGEX$ accepting $L$. We claim the $REGEX$ $E^{'} = E^{+}$ accepts L. i.e. $L(E^{+}) = (L(E))^{+}$
$L^{+}$ is regular since there is a $REGEX$ $E^{+}$ ...
0
votes
1answer
31 views
Create an Finite Deterministic Automata for a regular expression
I want to create a finite state machine that accepts the following language:
$$
L=\{w\in\{a,b\}^* | w \text{ contains abb but not on the first position}\}
$$
So I began by writing a regular expression ...
2
votes
1answer
56 views
Regular expression for all binary strings avoiding 0110
Consider the language
$$ L = \{ w : w \in {0,1}^* \text{ and } w \text{ doesn't contain } 0110 \text{ as a substring.} \} $$
What is a regular expression for this language?
I thought of $1(1)^*0(0)^*$....
1
vote
2answers
62 views
Proving some subsets of a regular languages to be regular languages
I have to prove that if a language $L$ is regular then:
a) $NONPREFIX(L)=\{u \in L / $none of the prefixes (not $\epsilon$ or $u$) of $u$ are elements of $L \} $ is regular
On this one I think I can ...
0
votes
1answer
36 views
How to check if a language is not regular?
I have the given regular language and i am suppose to check if it is regular and if it is, to provide a regular expression
However, if the language is not regular i have to prove using the "...
0
votes
1answer
18 views
Relationship between Kleene Star of a subset of regular language and the regular language
If $L(R_1) \subseteq L(R_2) \subseteq L(R_3)$ then $L(R_1)^* \subseteq L(R_2)^* \subseteq L(R_3)^*$. Does this also imply that $L(R_1)^* \subseteq L(R_3)$?
1
vote
0answers
54 views
How to prove a statement in regular expression?
I cannot figure out how to go about proving this statement in regular expression.
$$ L(R_1) \subseteq L(R_2) \subseteq L(R_3) \implies L(R_1^*+R_3)^* \subseteq L(R_2^*+R_3^*) $$
Here's what I have ...
0
votes
0answers
35 views
Regular expression for all binary words avoiding 11
I am reading a book example on regular expressions and I have a trouble to get why the answer is correct.
"Write a regular expression for the regular language that contains all the strings by 0's ...
0
votes
0answers
23 views
All string matches for regular expression [duplicate]
Given a regular expression, the ask is to find all matches in a string, str.
Most implementations give longest match only. For example, [\d]* in str "123456", the regex libraries in C++ or ...
0
votes
1answer
58 views
Convert finite automata to regular expression
I am trying find the regular expression that describes the finite automata in the image below.
Given the following finite automata
which of the following regular expressions describes the same ...
0
votes
0answers
10 views
I'm having some trouble converting a FA to a RegEx [duplicate]
I was reviewing some of the material that I found about FA to RegEx and while I was practicing with one or another conversion, I came across this FA that I could not pass to RegEx. Would someone be so ...
1
vote
2answers
58 views
Is $L = \{ w : \#_a(w) = \#_b(w) \}$ regular?
Is $L = \{ w : \#_a(w) = \#_b(w) \}$ regular? I do not think it is. I recently posted a question and from there I was thinking if this language is regular.
If we assume on the contrary, then there ...
1
vote
2answers
24 views
Operations without common elements can not be generated using a finite state automata
I heard that some operations involving regexes that do not have common elements can NOT be generated using a finite automata. I do not remember what it was, where it was from, can anyone tell me what ...
0
votes
1answer
79 views
Is (a+b)* and (ab)* same in finite automata?
Regular language of (a+b)* and (ab)* are:
(a+b)* = { ε, a, b, aa , ab , bb , ba, aaa, ...}
(ab)* = { ε, a, b, aa, ab, ba, bb, aaa, ... }
I am new to Finite automata and this simple notion is ...
0
votes
1answer
34 views
Read regular Expression from NFA
Good evening everyone!
Can someone help me with the following task?
So we have this NFA:
I was supposed to create a regular expression out of it. Now the solution says: $a^{+}b^{+}(c|ca^{*}b^{+})^{*}$...
1
vote
1answer
119 views
What is the the pumping length for the regular expression (0+0001)((1111)*+(00)*)
I have this assignment question to find the pumping length of a regular language (L). The regular expression for the L is given as
$(0+0001)((1111)^*+(00)^*)$
What is the length of the longest string ...
0
votes
1answer
27 views
minimum number of states in cross product of two minimum DFAs
If FA1 and FA2 are 2 DFAs with minimum number of states. I want to find cross product DFA (FA1XFA2). Will the cross product DFA obtained from 2 minimum DFAs also have minimum number of states(num of ...
-1
votes
1answer
26 views
Proving of regular language [duplicate]
Is this regular or not
L = {w1w^R | w ∈ {0,1}*
(where for any word w ∈ {0,1})*, w^R denotes the reverse of w)
1
vote
1answer
103 views
What does “lookahead” refer to?
I keep hearing about lookahead parsers, LL parsers, LR, LALR, etc... but no clear explanation behind the etymology of this word.
What does "lookahead" refer to? How does this relate to LL, ...
1
vote
2answers
71 views
How to prove that concatenating a language A and A* is commutative?
Suppose we have a language $A$. I want to prove that $AA^*$ is commutative. I know that this expression equals $A^+$, but I'm not sure how to go about a proof yet. This is my attempt so far.
If $A$ is ...
3
votes
1answer
184 views
Complete explanation of state elimination methods [duplicate]
I'm so sorry if this question is too general, but I need to understand the general process of the "State elimination method".
In other words, what is the general idea, and what is the ...
6
votes
1answer
2k views
Is it possible to build any regular expression in a computer language with just 3 basic operators?
Many computer languages have complex regular expressions tools. For example, in Javascript you have global flags, escape characters, whitespace character, assertions, character classes, groups and ...
0
votes
0answers
45 views
Converting a regular expression to a grammar and regular grammar
I am working on a pretty small lab for my university course and I'm having trouble converting a given regex into a set of regular definitions, then into a grammar and finally a regular grammar. I have ...
0
votes
0answers
25 views
Regular expressions accepted by programming languages but are not regular [duplicate]
The below definition of Regular Language is given in Wikipedia.
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language ...
0
votes
0answers
51 views
a^ib^jc^k, i < j < k is a context-sensitive language, how can prove it as a context sensitive
I've been pondering this question for a long time, that $a^ib^jc^k, i < j < k$ is a context-sensitive language, how we can prove it to be context sensitive or
which grammar can generate such a ...
0
votes
1answer
40 views
How to apply Arden's theory to determine a regular expression
If $P=ab$ and $Q=a^*$,
how do I use Arden's theorem to determine the regular expression $R$.
I'm not sure if I am supposed to just substitute the values of $P$ and $Q$ in the equation $R= Q + RP$. ...
0
votes
2answers
41 views
Can a regular expression be any string from the language described by it? [closed]
Is it possible to have a regular expression from a language (that has strings of infinite length) which it describes ?
0
votes
0answers
29 views
Constant single match regex
I am looking for the name (definition?) of X in:
A regular expression is X iff it has exactly one possible match.
Examples: <empty regex>, abc, ...
2
votes
1answer
63 views
Extracting regex submatch boundaries without backtracking
I'm attempting to develop from scratch a simple regex engine. I would like for my engine to have the ability to report, "The regex matched on a substring of this line starting at index and ...
1
vote
1answer
44 views
Regular expressions
I am new to theoretical cs and am working through it slowly. I have completed a simple question and was wondering if my answer is correct or not. Thank you kindly for any feedback.
The question is:
...
1
vote
2answers
63 views
Does a regular expression exist for any number that contains no more than two 5s and no 6 twice in a row?
For example, a valid number would be 6165156 and an invalid number would be 1566515.
I have tried many times to construct a finite state machine for this with no success, which leads me to believe the ...
0
votes
1answer
109 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 \to Α Β S $
$ A \to S $
$ B \to a B b $
2
votes
1answer
49 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
34 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
38 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
25 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.
5
votes
1answer
287 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
39 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
71 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 ...
1
vote
1answer
32 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
30 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
40 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?
