The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
18 views

Arden rule proof

I'm studying Arden's Rule for regular languages, but I'm having troubles with the proof. Arden's rule states that the set A*⋅B is the smallest language that is a solution for X in the linear equation ...
1
vote
1answer
15 views

Is Σ* the same as saying L*

I'm getting confused over the two. Are they the same? The complement of a language L is Σ* - L. Is saying L* - L wrong?
0
votes
1answer
9 views

Proving that a language with a regular expression is context-free

If L = {ww : w ∈ L(1*01*)} it means that w = $1^a$0$1^b$ and ww = $1^a$0$1^b$$1^a$0$1^b$ If I want to prove that this language is context-free by giving a context-free grammar, can I give a CF ...
0
votes
1answer
22 views

Regular expression

I'm trying to find Strings of length 4 In this regular expression. However, I'm having trouble understanding how the string is built $$1(1+00)^*0+(01)^*+(101+0)(10+λ)1^*$$ For example, for ...
1
vote
1answer
46 views

Find regular expression that defines a given language

I want to find a regular expression that defines a language L over the alphabet {0,1} with a following condition: every word contains exactly two 000 substrings. For example, a valid word would be ...
0
votes
1answer
34 views

How would I draw a state transition diagram to satisfy this regular expression?

I somewhat understand finite state machines in concept however am unsure how I would apply it in this example. The question is Draw the transition diagram of a finite state recogniser which accepts ...
0
votes
1answer
27 views

Regular Expressions that define given languages

A few of these here I just wanted to make sure I had right. For $\Sigma = \{0,1\}$ a. The language consisting of all strings of 0's and 1's that have even length and where 0's and 1's alternate I ...
2
votes
3answers
61 views

The number of elements in a set

I have a small task, part of my homework, which tends to confuse me because of its simplicity. It makes me think that I am missing something. I have to find the number of elements in the set {w | w ∈ ...
2
votes
1answer
17 views

Finding regular expressions for which a given Turing machine halts and accepts, halts and rejects, and diverges.

Consider the Turing machine M = (Q,Σ,Γ,δ,q,F) F = {t} Q = {q,r,s,t,v,x} Σ = {a,b,c} Γ = {B,a,b,c} δ = [q,a,q,a,R] [q,b,q,b,R] [q,c,v,b,R] [q,B,r,B,L] [r,a,s,B,L] [r,b,s,B,L] [r,c,s,B,L] ...
0
votes
2answers
51 views

Describe as a regular expression the set of strings over {a,b,c} that contain the substrings aa,bb,cc

What would be an appropriate regular expression for this set of strings listed in my title? i have this so far: (aa,bb,cc) is a subset of all the strings listed (a,b,c) (it corresponds to the strings ...
0
votes
1answer
22 views

Constructing regular expressions for languages

I'm new to regular expressions and I'm currently working on some exercises to get familiar in constructing regular expressions for languages. I have the following languages, for which I already tried ...
0
votes
2answers
14 views

Languages and their Regular Expressions - Automata

I am working on some Automata practice problems. I am working a 2 part question. Here it is: Let $\Sigma = \{a,b\}$ be an alphabet. Let $L = \left\{w \in \Sigma^* \mid n_a(w) \le 4\right\}$ ...
0
votes
1answer
20 views

What is $h^{-1}(L)$, for $L$ a regular language and $h$ a homomorphism?

Let $L = L((00 + 1)∗)$ and $h : \{a, b\}^* \to \{0, 1\}^*$ be defined by $h(a) = 01$ and $h(b) = 10$. What is $h^{−1}(L)$? In this context "$+$" means "$\cup$". So the language $L$ is all the ...
2
votes
2answers
43 views

A Regular Expression for all strings that…

I got a problem I have to solve, the problem says that given an alphabet $\Sigma = \{a, b, c\}$ I have to build a regular expression that describes the string with: An even number of a's. A 4k + 1 ...
0
votes
0answers
26 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 ...
2
votes
1answer
35 views

Equivalence of regular expression

Let $ A = \{a,b\}$ be an alphabet. Please hint me with show, that this regexes are equivalent. That means, we should show that: $L(e_1 )= L(e_2)$ 1) $(a^*b)^*a^* = (a+b^*)^*$ 2) $(a+b^*)^* = ...
1
vote
1answer
29 views

Difference between regular and not regular languages

I don't understand the difference, in classes I've seen the pumping lemma for regular languages and I know how to apply it to demonstrate whether a language is regular or not, but I feel that I don't ...
2
votes
1answer
52 views

NFA to DFA and Regular Expression

The truth is that my teacher gave us a homework, and I wanted to ask you if I did this right. What I have to do is answer the following questions given the following NFA. Why is this an NFA? What ...
1
vote
1answer
69 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 ...
0
votes
1answer
44 views

Proving an operation is closed under regular languages

Following operation is defined over languages where $n \in \mathbb{N} :$ $L \ominus n = \lbrace s \in \sum^* | \exists s^{'} \in \sum^* (length(s^{'})=n,ss^{'} \in L) \rbrace$ Meaning that $L ...
1
vote
2answers
40 views

Proving {0^n 1^n 2^n | n >= 0} is not regular

This is not a homework assignment, but something I'm reviewing. I need to prove that $0^n 1^n 2^n$ where $n \geq 0$ is not regular (Just the DFA, not related to CFG). I feel like this is similar to ...
0
votes
1answer
43 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 ...
1
vote
1answer
42 views

Write the regular expression of the language that the DFA accepts.

I am given a DFA and I have tried to write the regular expression of the language that it accepts. This is the DFA that I am given: I have found some words that the DFA accepts: ...
0
votes
1answer
47 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
2answers
35 views

Finding the regular expression

I have the problem below: I need to find the regular expression of the set of strings where $n(a)+n(b)$ is an even number (where $n(a)$ is the number of $a$'s and $n(b)$ is the number of $b$'s) .. I ...
0
votes
0answers
28 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, ...
1
vote
1answer
46 views

Regular expressions

I have this assignment and I have to prove that $$ (b+aa^* b)+(b+aa^* b)(a+ba^* b)^* (a+ba^* b) = a^* b(a+ba^* a)b^* $$ How do I prove this? What I have is this: $$\begin{align} \text{LHS} ...
2
votes
0answers
33 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 ...
0
votes
1answer
56 views

Proving Reversal of a Language in Recursive Way

We define the $reverse$ of a string as follows: $(x_1x_2...x_n)^R=x_nx_{n-1}...x_1$ where $x_1,x_2,...,x_n \in \Sigma$. We can also define the reverse of a language by $L^R= \lbrace s' | \exists s ...
0
votes
1answer
20 views

Clarification on Lemma problem

I have trouble understanding this question. I have no idea where to start. Let $A$ be the set of palindromes over $\{a, b\}$. Suppose you are trying to prove that $A$ is not regular using the ...
0
votes
0answers
43 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
4answers
45 views

Regular Expression for Simple Language

I'm having trouble writing a regular expression given the following $\{a, b, c\}$ which produces the set of strings of length 3. I don't really understand how to restrict the length of the string. ...
0
votes
1answer
90 views

Which of the following sets are regular and which are not? Give justification.

Which of the following sets are regular and which are not? Give justification. a) $\{a^nb^{2m}\mid n\ge 0\text{ and }m\ge 0\}$ b) $\{a^nb^m\mid n\ne m\}$ c) $L((a^*b)^*a^*)$ d) $\{a^nb^nc^n\mid n\ge ...
0
votes
2answers
39 views

Regular expresson a's and b's

Need to construct a regular expression that recognizes the following language of strings over the alphabet {a,b}: - The set of all strings over alphabet {a,b} in which every occurrence of b is ...
0
votes
0answers
29 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
1answer
34 views

Regular Expression of alternative 0's and 1's?

Let $L$ be the language of $0$'s and $1$'s in alternate positions, where $$ L = \{ \epsilon, 0, 1, 01, 10, 01010,\ldots\}. $$ Is $(0)*$ + $(1)*$ a valid regular expression that represents this ...
2
votes
1answer
42 views

regex for binary string which doesnt contain 11110

Here's my attempt, although I'm not sure if i missed any edge cases: $(0,10,110,1110)^*(1)^*$ it seems to work for any random string i test in a regex program, but is this correct?
-2
votes
1answer
40 views

What is the Regular Expression for this DFA? [closed]

What is the Regular Expression for this DFA?
1
vote
1answer
11 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
17 views

Isn't $L=\{ww|w \in \{0,1\}^*\}$ a Non Deterministic Context Free Language?

My book says that it is not a Non Deterministic CFL. If $ww^R$ can be a N-CFL, then why not the one in the question? I think it might be a printing mistake, not sure.
1
vote
0answers
34 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
1answer
170 views

Blocks of Pyramid Pattern Expression [duplicate]

There is a pattern following, and trying to find the algebraic expression Each layer (from the top). Diagram. So the first layer has 1, second has 4, third has 9, and the fourth has 16. That's ...
1
vote
2answers
33 views

Did I find the right expression for the regular language for this FSA?

I have the following FSA, and the regular language that I found for it: Is this language correct? It doesn't match the solution in the book, but my teacher says there can be multiple equally ...
2
votes
3answers
52 views

regular language proof, a language partial to a regular one

So, I've been trying to solve a question I got and I think I'm correct but I'm not positive. Is the language {w| www belongs to L' and L' is regular} regular? I couldnt find any way to prove it isnt ...
0
votes
1answer
53 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
33 views

Binomial theorem - number of terms in expansion

Question: Find the number of terms, after simplifying, in $$(x + y + \frac{1}{x} + \frac{1}{y})^{16}$$ I was unable to find any approach to this question. Fully expanding the expression isn't a ...
1
vote
3answers
23 views

Expression of Equation

Find the next three terms for the pattern following : (-1276),(+425),(-142),(+47) Simple pattern here.... Only pattern I can find is that, the odd number term goes up by 1134, and the even number ...
1
vote
5answers
34 views

Finding expression for pattern

This seems easy.... Pattern: 3, 6, 10, 15, 21.... How do I find expression for this? It looked easy, but I couldn't find it. I tried graphing it, but it turned out that it is not quadratic... ...
0
votes
1answer
23 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
2answers
43 views

Regular expression 00 or 11 not both

Can anyone help me with this question: I know it before, but I have tried to solve it myself and didnt succeed. what is the regular expression for this language: L=all words that have 00 or 11 but not ...