Questions tagged [regular-expressions]
Questions about regular expressions, a formalism to describe regular languages.
586
questions
0
votes
0answers
11 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
11 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 ...
-1
votes
0answers
14 views
Regular Expression Kleene Star application - using 0s and 1s
Have a question from an online course I am trying to take for a certificate. Came across a few questions like this and need help working through the problem and the rationale to get the solution. Any ...
0
votes
0answers
38 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
31 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
37 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
55 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 ...
1
vote
1answer
36 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
58 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
44 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
24 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
52 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
27 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 ...
0
votes
2answers
79 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
37 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
121 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
79 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
93 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
36 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
63 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
13 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
33 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
61 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
36 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
28 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^\...
1
vote
1answer
161 views
What's the difference between phi and lambda in regular expression?
I've been learning on Formal Languages and Automata of Peter Linz(6th edition).
In the chapter 3 of this book, it explains the primitive regular expression.
But I don't know what is the difference ...
7
votes
1answer
271 views
How hard is finding the shortest path in a graph matching a given regular language?
Suppose we are given a directed graph $G = (V, E)$ with edge weights $w : E \rightarrow \mathbb{R}$ (we can assume there are no negative cycles) and edge labels $\ell : E \rightarrow \Sigma$ from some ...
0
votes
1answer
51 views
How create DFA with multiple finished states for lexers?
Is possible to create DFA directly from regular expression. But for lexical analyse is needed "joined" DFA with many finish states, for example one state for string, one for integers, one for floats ...
1
vote
1answer
91 views
Is there a meta text processing concept in CS?
I understand that text processing could be done in various ways on top of operating systems:
Shell utilities for processing a file (and/or a file name): tr, ...
0
votes
1answer
45 views
Language to regex
Let A={a,b}.
So the question is to write regular expression such that L(r) which consists of all words.
My answer is this:
L(r)= (a+b)* a* b* (a+b)*
Is this ...
-1
votes
2answers
120 views
Uniqueness of solution in Arden's theorem
Geeksforgeeks contains a proof of Arden's theorem, asserting that $R=QP^*$ is the unique solution to $R=Q+RP$. The proof is reproduces below.
My question is:
What is the logical reasoning to prove ...
3
votes
1answer
36 views
Converting DFA to RE with Arden's Rule
So I've searched around and found the algorithm to do so: How to convert finite automata to regular expressions? and I decided to test out the second-level response, Raphaels, and while I was getting ...
3
votes
1answer
114 views
Regular expression for strings not starting with 10
How can I construct a regular expression for the language over $\{0,1\}$ which is the complement of the language represented by the regular expression $10(0+1)^*$?
3
votes
1answer
61 views
Prove the equivalence of regular expressions
I have a question relating to regular expressions that I'm a bit confused about, If someone can help me out, that would be very much appreciated.
Suppose there exists regular expressions R, S and T.
...
0
votes
0answers
13 views
Regular Expression for a^nb^m such that n<= m+3 [duplicate]
I want to know if its possible to write a regular expression for a context free language:
For example I have a language : L={a^n b ^m: n<= m +3}
I have written the following regular expression ...
0
votes
0answers
56 views
Regex Questions?
I need to match all words having two adjacent vowels that differ.
I did this /\b(?=\w*([aeiou])(?!\1)[aeiou])\w+/ but I am not allowed to use the ?! and it needs to be done in as few characters as ...
0
votes
2answers
19 views
Regular expression containing lambda
What is the meaning of lambda here:
$$(b+c)^*(a+\lambda)(b+c)^*(a+\lambda)(b+c)^*(a+\lambda)(b+c)^*$$.
I know that lambda is used in the context of NFA?
Let's suppose we break down the expression ...
0
votes
0answers
19 views
Is this language regular or not regular {(a* union b)a } intersection {a*b*} is a regular language [duplicate]
Is {(a* ∪ b)b } intersection {a* b* } a regular language?
4
votes
1answer
68 views
Can every regular expression be written as sum of products?
I was trying to prove that Parikh Image of every regular language is semi-linear. Even though it is true for CFL, but this question was about regular languages.
To prove this, I decided to proceed as ...
1
vote
0answers
45 views
Is ASM a regular language?
I'm giving a presentation where I have a single slide dedicated to formal languages. In this slide I give a simplified overview of the Chomsky Hierarchy and I'd like to give an example of a real world ...
1
vote
1answer
47 views
Different application of Arden's theorem leads to different answers
So, I have to solve for the following set of equations
$q_1$ = $q_1$a + $q_2$b + $\epsilon$
$q_2$ = $q_1$a + $q_2$b + $q_3$a
$q_3$ = $q_2$a
There are two ways to do this.
I did this
...
0
votes
0answers
26 views
What exactly is “pattern matching”?
I know some examples of "pattern matching". E.g. in the context of functional programming, and regular expressions.
But is there a precise definition?
In particular, it seems that it has to do with ...
1
vote
0answers
36 views
Regular expressions for set of all strings on alphabet $\{a, b\}$
I came across following regular expressions which equals $(a+b)^*$ (set of all strings on alphabet $\{a, b\}$):
$(a^*+bb^*)^*$
$(a^*b+b^*a)^*$
$(a^*bb^*+b^*ab^*)^*(a^*b+b^*a)^*b^*a^*$
I want to ...
0
votes
1answer
45 views
Regular expression and Right Regular grammar for decimals starting with 1 ending with 9?
I was trying to do the following:
Consider the set of all strings over the alphabet {0,1,2,9} that are decimal numbers beginning with 1 and ending with 9 and having exactly one decimal point (.). ...
0
votes
0answers
33 views
What is a Regular BNF Grammar and a Regular Expression for (simple) Resource Identifiers?
I was trying to make a regular grammar for resource identifier described as follows:
Consider the set of all strings over the alphabet $\{ a, b, / , . \}$
that represent an RI (resource ...
-2
votes
2answers
68 views
$L_1 ∩ L_2$ is not regular while $L_1$ is regular and $L_2$ is not regular language
Could you give me an example of languages $L_1$ (regular) and $L_2$ (not regular) where $L_1 \cap L_2$ is not regular?
3
votes
3answers
336 views
Regular Expression with at least one a, even number of b
I've been working on some regular expression questions, and came across one that I cannot figure out. Working on the language over $\{a, b\}$, the text asks for a regular expression for the language ...
5
votes
3answers
894 views
How to determine minimum word length of regular language
Given a regular language $L$ and a regular expression $r$ with $L=L(r)$. Is it possible to determine the minimum length of words of $L(r)$ by the structure of $r$?
A straightforward example:
Let's ...
0
votes
0answers
8 views
Binary string regex problem, starts with a 1 and has an even number of 0s [duplicate]
I am trying to make a regex expression that is:
A binary string that starts with a 1, and has an even number of 0s.
I tried, 1(1*01*01*)*, but it misses the case where it is 11. How would I go about ...
3
votes
3answers
148 views
Are regular languages and their regular expressions part of computer science?
I am trying to understand if regular languages and their regular expressions are concepts of computer science in general and if these are discovered, or invented, by computer scientists, in particular....
