The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
2answers
46 views

Concatenation of strings

We have two strings A and B. We have to find if for some n,m A concatenated n times equals B concatenated m times or not. I have made an interesting observation but am unable to prove it.It appears ...
0
votes
2answers
70 views

Algorithm for a regular expression

This was a question for an exam that I received 0 points on, I'd like to get some input on what the correct answer should have been. Imagine that you are asked to write an algorithm P that takes a ...
2
votes
1answer
589 views

Complement of a regular expression?

What is the regex for the complement of $r = b^*(ab + a^* + abb(b^+))^*$ ? I am thinking $(a+b)^*(abb)^+a^* $ since anything that contains $abb$ and is not followed by $b$'s would not be accepted ...
2
votes
1answer
75 views

Build regular expression from language

I have the following language: L = {w $\in$ {a,b}* | aa is not part of w}. I have to construct a regular grammar from this language and I thought about first finding the regular expression from the ...
1
vote
1answer
46 views

Find regular expression for a given language

I need to find a regular expression for the following language: $$ \Sigma = {\{a,b,c}\} $$ define $L$ to be the language of all words over $\Sigma$ that contain the substring $aba$ odd number of ...
1
vote
1answer
10 views

Regular expression building: Comment delimited strings

I'm attempting to build a regular expression that will accept only strings of the form: ...
1
vote
1answer
456 views

Finite state machine

I am doing discrete math, and we are studying Finite State Machines. But i am a little confuse on how to do this. Here is a question, Write a regular expression for the language, and define a finite ...
1
vote
1answer
90 views

Complement of a Set of Strings in a Language

Suppose $B= \{ 0^n1^m2^{n-m}:\, n\ge m\ge 0 \}$ Is the complement $\overline B = \{ 0^n1^m:\, 0\le n\lt m\}$? Or is it the universe of all possible strings (including all strings with symbols ...
1
vote
1answer
35 views

Regular languages that are stutter-invariant but not star-free (LTL/FO-definable)

I am looking for simple examples and/or general ideas on regular languages (I am interested in finite words and infinite words alike) that are stutter-invariant (a language $L$ over an alphabet $A$ is ...
0
votes
1answer
34 views

$L_1 =(a^nb^n)$ and $L_2 =(a^nb^{2n})$. Is $L_1 \cup L_2$ DCFL?

I think that since $a^nb^n$ is not regular (applied pumping lemma), so is $L_2$. Therefore, $L_1 \cup L_2$ is not cfL. Is that correct?
0
votes
1answer
19 views

Are regular expressions in mathematics related to PCRE or POSIX regexps?

I've recently come across a number of questions tagged with (regular-expressions), and talking about some type of regular expressions, here's an example of such ...
0
votes
1answer
31 views

Proving non-regularity of a language

How can I prove $L = (01^n2^n | n\geq 0)$ is not regular? Would it be sufficient to say that $01^p2^p$ is in $L$ and by pumping lemma, $01^p2^p$ can be written as $xyz$ such that $|y|>0, ...
0
votes
1answer
21 views

converting to regular expression

{w | w can be written as $0^k l 0^k$ for some $k \geq 1$ and for any $l$ in ${0,1}*}$ i.e. 00010111000 can be written as 0^3 10111 0^3 How can I convert this description into a regular expression? ...
0
votes
1answer
26 views

Proof the 1 language is contained in another

Does anyone know what the best method is to prove that the intersection of Language1 and Language 2 = Language1? Where both languages are over alphabet {a,b,c}.
0
votes
1answer
16 views

Finding a Regular Expression with a Specific Length from a language

Given this language, I was supposed to find the Regular Expression that represented it. Having given up and getting the answer later (below) I couldn't understand the regular expression. Given ...
0
votes
1answer
19 views

Regular expression for a particular language

Several years ago I came across a paper that defined a regular expression (or collection of regular expressions?) for a specific language. The language is the language of set partitions enumerated by ...
0
votes
1answer
68 views

Find Regular Grammar from NFA

I'm currently doing some self study to improve my half-forgotten college theory of comp skills. I'm going over some problems from an old book and it asks you to find a regular grammar for the ...
0
votes
1answer
278 views

induction to prove regualr expression

Prove that is if S and T are any regular expressions over the one-letter alphabet, (for example: Σ = {a}), and if n is any natural, then the languages (ST)^n and (S^n)(T^n) are equal. I have to use ...
0
votes
1answer
574 views

Palindrome Decidable by DFA

Here's a problem a professor I was talking with gave to me to see how people solve. How would you solve this? A string in {a,...,z}* is said to be a palindrome if it is equal to its own reversal. Is ...
0
votes
1answer
40 views

Mathematical expression of largest $k$ numbers from $n$ numbers $(n>k)$

Can someone provide me a Mathematical expression of largest $k$ numbers from $n$ numbers $(n>k)$ eg $S$ is a 3x3 matrix with [6 8 5 ; 3 4 6 ; 9 0 5] where $n$ = 9 (elements) and I need to ...
0
votes
1answer
25 views

Need help with the steps

Tried this problem several times and still cant get the right answer. Please help! https://webwork2.uncc.edu/webwork2_files/tmp/equations/ba/00ebd18c83856ce9c3b184a9a058a01.png
0
votes
1answer
85 views

Is this NFA correct?

For the language L = $\{\Sigma^*. 0 .\Sigma^5 . 1. \Sigma^*\}$ The NFA must have 8 states. Also, what would be the upper bound on the number of states of a DFA recognizing L.
4
votes
0answers
69 views

How to write a regular expression?

I am trying to write a regular expression for the set of all strings in Σ* that starts with an even number of b's and contains at most two a's. The language contains only a's and b'. This is what I ...
2
votes
0answers
29 views

Regular expressions and equality

Is the equality true or false? $(r^*s^*)=(r+s)^*$ My Approach: Assume the alphabet used is {0,1}$^*$ Equality is false: If r = 0 and s = 1 Then if 0101 $∈$ $(0 + 1)^*$ this is true because ...
2
votes
0answers
48 views

how to covert regular expression in simplest form?

I have made this expression from nfa (NFA to regular expression) : (a+ab+aa*b)*(a+a*a) but at book answers it is written like this : (a+aa*b)*(a*a) I am thinking that the my answer is same as ...
2
votes
0answers
239 views

Regular Expression For Set of Strings Not Containing OOO

The following is my attempt at coming up with a regular expression for the set of binary strings that do not contain $000$: $(1 + 01 + 001)^*(\epsilon + 0 + 00)$ I'm going to need it for a ...
1
vote
0answers
29 views

Why is $a^nb^n|n\geq1$ not regular and $a^nb^n|n\leq {10^{10}}$ regular?

I've heard somewhere that since the latter is bounded, it is regular. Can anyone explain me what a bound actually means? And if the latter is regular, then how would you write the regular expression ...
1
vote
0answers
18 views

Equality of regular language

I am showing that two regular expressions are equal. In one of intermediate steps, I thought of the equaility: $$(RS+R)^* = (RS)^*R(RS)^*R(RS)^*....R(RS)^* = R^*(RS)R^*(RS)...R^*$$ Is it true? I ...
1
vote
0answers
62 views

Minimal DFA for a given regular expression

How can I construct a minimal DFA from the following definition? $L=\{w \in \{a,b,c\}^* $: if the second-to-last letter from w is an $a$, then the number of $c$'s $\le 1\}$ I've already made a ...
1
vote
0answers
39 views

Example of a Regular Map

I am working with Shafarevich's "Basic Algebraic Geometry 1". Example 1.15: The map $f(t)=(t^2,t^3)$ is a regular map on the line $\mathbb{A}^1$ to the curve given by $y^2=x^3$. I am not ...
1
vote
0answers
47 views

Calculating the variance of the a regular expression assuming position dependent

Hello I am having trouble with a slightly biological problem I am given a regular expression $- [RK]-[LV]-[DE]-x(2)-Y$ this expression means that there is a string with the first position being an ...
0
votes
0answers
19 views

Derivation: Discerning difference between arithmetic expression with parenthesis versus without using abstract syntax trees

I am trying to illustrate the expression: ( 3 * 4 + 5 * 6 + 7 ) using an abstract syntax tree. I have already illustrated the expression: ( 3 * (4 + 5) * (6 + 7) ). Could someone please illustrate ...
0
votes
0answers
29 views

Convert the regular expression to a NFA

I have to convert the following regular expressions to a NFA: $$(0 \cup 1)^{\star} 000 (0 \cup 1)^{\star}$$ $$(((00)^{\star} (11)) \cup 01)^{\star}$$ $$\emptyset^{\star}$$ $$a(abb)^{\star} \cup ...
0
votes
0answers
29 views

Proving that two expressions are equivalent

So, I'm working through some proof exercises, and one of the questions is about the following regular expression: (a|b)* = a*(a|b)* if they are equivalent, prove ...
0
votes
0answers
26 views

One-to-one correspondance between regular sets

I have problem with one-to-one correspondance "One-to-one correspondence with the set (B) of all tags possible being represented with their binary representation (i.e. 0, 01, 00, 010101, 11000, ...
0
votes
0answers
38 views

Does there exist a regular expression for a series of points?

If I was looking for a certain "shape" or "pattern" in a simple line chart is there a way to describe the series of points that would make up this "shape"? Example: If I had a line chart and I was ...
0
votes
0answers
24 views

Regex - Ternary number that leaves a remainder of 3 when divided by 4

I need to find the regular expression behind: L = {α ∈ {0, 1, 2}∗ | α leaves a remainder of 3 when divided by 4 and is a ternary number} Any help would be greatly appreciated!
0
votes
0answers
15 views

find the intersection of two regular expressions

I have a language A which is described as $a^*b+c^*$ in which the alphabet is $\{a,b,c\}$. I define a new language which is: $A_{1/3}=\{xz|xyz \in A , |x|=|y|=|z|\}$. I want to find the intersection ...
0
votes
0answers
27 views

productions with identical right hand sides for different nonterminals

Can a regular grammar contain two productions with identical right hand sides? I know in context free grammars shift reduce parsers issue reduce reduce conflicts when smth like this happens. What are ...
0
votes
0answers
36 views

How to write a Regular Expression

I have seen that the regular expression for the set of strings beginning with a and ending with b is written as a(a+b)*b Can some one tell me how to write this
0
votes
0answers
65 views

Regular expression of: $\{ w \in \Sigma^* : w \text{ does not contain the substring 110} \}$.

Given $\Sigma = \{ 0,1,2 \}$, write a regular expression for $$\{ w \in \Sigma^* : w \text{ does not contain the substring 110} \}\;.$$ I know how to do a regular expression for a language that does ...
0
votes
0answers
492 views

regular expression and intersection

I have this language L that contains only one string: $a_{1}a_{1}a_{2}a_{1}a_{1}a_{2}a_{3}a_{1}a_{1}a_{2}a_{1}a_{1}a_{2}a_{3} ....a_{n}...a_{n}$ written more concisely ...