Questions tagged [regular-expressions]
Questions about regular expressions, a formalism to describe regular languages.
518
questions
0
votes
0answers
14 views
Create automata from non regular grammar
I have two grammars:
L → ε | aLcLc
L → ε | aLcLc | LL
This two grammars are equals but the first one is regular, so it produces a regular language and a ...
1
vote
1answer
49 views
Write down a DFA for the regular expression (000* + 111*)* and explain why it cannot have lesser number of states
So, I came up with a DFA for the regular expression. Now for every string described by the regular expression, the DFA accepts it. But in order to ascertain if it's really a DFA for the regex, you ...
0
votes
0answers
19 views
How to write ^ (to the power) in regex in PFLAP [closed]
I am trying to convert this regex to NFA
(3^+)(3*+2*)(1^+)(2+1)*3*(2^+ )(3+1)*(3+1)*2*
but it says "Operators are poorly formatted!"
So, the question is: does ...
1
vote
2answers
81 views
How do i tell if a grammar is regular or not?
I know that a regular grammar has a definition
$$\begin{align}S &\to aS\\
S &\to \lambda
\end{align}$$
But I dont really know how to apply this information to check whether or not a grammar ...
0
votes
1answer
22 views
Union and Difference of languages generated by grammar [closed]
So I have two languages $L = \{ w \in \{a, b \}^{\ast} \ | \ w \ \text{contains an odd number of a's} \}$ and $L^{\prime} = \{ w \in \{a, b \}^{\ast} \ | \ w \ \text{contains at least two a's} \}$.
...
0
votes
1answer
23 views
Need help understanding regular expressions
I was reading up about formal languages (see here: https://pdfs.semanticscholar.org/18b2/d685d5e244a6bfc5a31d312f1e8d322c16a9.pdf) and got confused when I started reading about this expression: 0(0+1)∗...
-2
votes
1answer
37 views
Regular Expression: Writing an expression with at least two characters in length? [closed]
A past exam question:
(1) Consider the language, $L$, of strings over the alphabet $\{x, y\}$ of length at least 2 with the second symbol being $x$. For example, $yx$, $xxyy$, and $yxy$ are members ...
0
votes
0answers
39 views
Regex to match number ranges less than a certain number
I'm trying to write some code to match numbers below certain bounds. I would much appreciate nay help somebody could give, I'm pretty lost with this one...
NB. I've checked the forums and can find ...
0
votes
0answers
26 views
Converting DFA to RE [duplicate]
I have been trying to solve this problem.
Convert the DFA to a regular expression.
I extracted these following equation.
$q_1 = q_2a$
$q_2 = q_1a + (a+b)q_3$
$q_3 = q_1b + q_2a $
Also,the ...
1
vote
1answer
32 views
Kleene Star regex question, sed behavior? [closed]
Kleene Star with 'sed' is behaving as expected for me, with exception of a case where the input pattern is "ab" and the regex is "b*". Does anyone know why this regex is not being matched against the ...
0
votes
1answer
40 views
find derivation trees for CFG
I need to draw the derivation tree for $1-2-(3-4)*5*6$ from the grammar below.
I want to know how many possible derivation trees are there from this grammar.
$$\begin{align}V_n&=\{expr,term,...
2
votes
1answer
22 views
Why $P$ cannot have NULL string in Arden's Theorem?
Arden's Theorem says that in the equation $R=Q+RP$, the $P$ cannot have NULL string. In this respect,the theorem will not be valid for the expression $R=Q+R(NULL+01)$. Am I correct? If so, then what ...
3
votes
2answers
92 views
Converse of pumping lemma for regular expressions
I want to come up with a language that satisfies the pumping lemma while not being a regular expression.
I thought of $\{0^i1^j: i > j > 0\} $. The pumping seems to work just fine, and this is ...
0
votes
0answers
18 views
regular expression with kleene closure [duplicate]
my question is if my regular expression R is 1* that means the language accepted is {^,1,11,111,1111...}
in that case i don't understand the meaning what (R*)* means
0
votes
1answer
23 views
Counting number of states from a regular expression
Given the regular expression: $r=ab+((a+\epsilon)c^*)^*$.
Let A be a non-deterministic automaton that accepts the language of r.
How many states are in A?
Answer the question without building A ...
1
vote
1answer
24 views
A deterministic FA for $0^*1^*$ is required
A deterministic finite automaton without $\epsilon$ steps for the language $0^*1^*$ is required.
Any nice picture ? I have created a NFA for this language which has 2 states $Q_1,Q_2$,
both are ...
0
votes
0answers
49 views
How generate regular expression on the alphabet {a,b}?
How can I write a regular expression that denotes language on the alphabet {a,b} of the strings that do not present "b" consecutive and the total number of "a" is multiple of three?.
2
votes
1answer
10 views
Regular expression notation clarification
For the alphabet $Σ$={a,b,c}
I was wondering how you would say:
T that has elements from Σ, so could be T=a, T=bc
I was considering maybe $Σ^*$ or $Σ^+$ would describe that, but I am not sure ...
2
votes
1answer
88 views
Finding a regular expression of a language
Our alphabet is {a,b} and we need to find a regular expression for the language of all words of the form $a^*b^*$, whose length is a multiple of 3.
Obviously $(aaa)^*(bbb)^*$ is one of the options, ...
0
votes
0answers
42 views
What is the best algorithm known to learn the regular expression from a set of positive examples?
I have a blackbox program that generates a set of strings. What is the best regular expression learner that I can use to learn (approximate) what the blackbox program uses as a generator? Note that I ...
2
votes
0answers
22 views
Regex NFA construction: Why use Glushkov over Thompson? Pros/Cons
In what circumstances should we prefer Glushkov's algorithm or Thompson's construction for the building of regular expression NFAs?
I understand the difference between them, and can follow the ...
1
vote
1answer
58 views
DFA multiple accepting states to Regular expression
I am trying to find the regular expression that defines this DFA, I am finding this particular case difficult since it has multiple accepting states.
If I understand this DFA correctly, it recognises:...
-1
votes
2answers
63 views
Regular Expression For The Language Σ = {0,1}
I have an language of Σ = {0,1} and need to find the the regular expression of:
Set of strings that have no pairs of consecutive zeros
Set of strings that contain ...
3
votes
1answer
49 views
Is there an algorithm to overapproximate a context free grammar by a regular expression?
I understand that a context-free grammar is strictly powerful than a regular expression in that a context free grammar can represent any regular language, but not all context free languages can be ...
2
votes
0answers
29 views
Transform Double Metaphone code into regex
I am using hyperscan to search through large texts for a lot of regexes. One addition should be selective phonetic search for individual words. The algorithm of choice is Double Metaphone (but please ...
0
votes
1answer
57 views
Regular Expression: L= {w | every even position of w is '1'}
I am trying to solve a regular expression of binary string where every even position is a '1'
I've solved this for an odd position: (1(0+1))*(1+ε)
How would it look like for an even position then? ...
0
votes
3answers
88 views
Define a finite automaton accepting the language below [duplicate]
$\{ w∈(a,b)^\ast | w $ does not contain '$ab$' as a subword $\}$.
About questions like this, I always want to construct the regular expression for it, then convert the regular expression to a finite ...
2
votes
1answer
21 views
Modelling regex replacement via a DFA
I wish to model the following common construction in code via a finite state automaton for the purposes of static analysis:
...
2
votes
2answers
54 views
Is intersection used in regular expression?
As union is part of regular expression in form of positive closure, similarly intersection is also a part of regular expression? in which form it can be used?
3
votes
2answers
36 views
Interpretation of this regular expression: (1*0*)*
Do the values of the two * inside the ( ) need to remain unchanged for every repetition of ( )?
For example, 110011001100 is part of this language set, but 1100100010 isn't?
Or can the values of the ...
0
votes
0answers
16 views
Arden theorem with 3 input [duplicate]
I have just started learning Arden's theorem to convert finite automata but I am stuck on its execution when we have 3 inputs.
Because I am not able to simplify any equation to have only 2 inputs ...
0
votes
1answer
45 views
Prove that the language is not regular [duplicate]
Prove that the following language $Σ = \{1\}$ is not regular.
$L$ = $\{w | |w| = k$, where $k$ is a prime number}.
How should one go about proving this? Should I use pumping lemma for this?
1
vote
1answer
23 views
I don't understand what this regular language is asking for? Find a grammar for L(G) = {w || w | is odd,∑ = (0, 1) }
I don't understand what this regular language is asking for? Find a grammar for L(G) = {w || w | is odd,∑ = (0, 1) }. What does the " || " mean I know a single " | " means or.
-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
votes
1answer
39 views
Regular expression for all possible strings. Does the Kleene star distribute over each element. (0+1)* = 0* + 1*?
Regular expression for all possible strings. Does the Kleene star distribute over each element. Is this true? (0+1)* = (0* + 1*) ?
1
vote
1answer
180 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 ...
1
vote
2answers
51 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
221 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 ...
0
votes
0answers
40 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
75 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 ...
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 + ...
1
vote
2answers
101 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 ...
1
vote
1answer
66 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 ...
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
43 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:
...
0
votes
1answer
29 views
Product of Lexical Specification
I have a problem that asks me to consider the string abbbaacc. I'm supposed to figure out which of the following lexical specification produces the tokenization ab/bb/a/acc.
The options are:
...
1
vote
1answer
48 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 ...
