The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
1answer
42 views

Pumping Lemma - Clarification of Usage

I'd like to make sure my understanding of the Pumping Lemma is correct. Consider $L=\{ 0^n1^m2^{n-m}:\, n \ge m \ge 0\}$ I'm going to give 2 solutions to prove that $L$ is not regular. One using ...
0
votes
1answer
69 views

Context Free Language [Prove Or Disprove]

Given the language below: $$L = \left\{w\in (a + b + c)^*: n_a(w) = n_b(w)\text{ or }n_a(w) \ne n_c(w)\right\}$$ How would I prove or disprove that it is either context free. I know that if it was ...
0
votes
1answer
81 views

Prove that a Language is Non-Regular Using Closure Properties

Use the closure properties of regular languages and a language $B$ known to be non-regular to prove that a language $A$ is not regular. My understanding is that the closure properties only apply when ...
3
votes
2answers
45 views

Injective map, that maps context-free languages to regular languages

Let $\Sigma \neq \emptyset$ be an alphabet. Is there an injective map $f: \Sigma^* \rightarrow \Sigma^*$ such that for every context-free language $L \subseteq \Sigma^*$ the set $f(L)$ is a regular ...
0
votes
1answer
129 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 ...
1
vote
1answer
56 views

If $L \cdot \{\epsilon, a, b\}$ is regular, is $L$?

Given that $L \cdot \{\epsilon, a, b\}$ is regular, is $L$ regular too? (Our alphabet is $\Sigma = \{a,b,c,d\}$ What I thought was yes, and here is why: If it is regular, then we know there ...
1
vote
1answer
53 views

About described DFA

I need to find DFA (or NFA, $\epsilon$-NFA, it's not improtant (I know how to convert between them)) that accept all strings of $0$'s and $1$'s such that every block of five consecutive symbols ...
1
vote
1answer
36 views

Myhill-Nerode Theorem with constraint

I am trying to to understand the Myhill-Nerode Theorem with the example. $L = \{{0^i1^j}|\ j > i\}$ I have read some article but still cannot fully understand,what I know about is that I have to ...
0
votes
1answer
70 views

Prove/Disprove: $vwvw=vvww$ iff $\{v\}^*\{w\}^*=\{vw\}^*$

Let $\Sigma$ be an alphabet and $v,w\in \Sigma^*$. I'm trying to prove that: $$vwvw=vvww\quad\text{iff}\quad\{v\}^*\{w\}^*=\{vw\}^*.$$ I tried to do it by induction, with no success. Any help will ...
0
votes
1answer
16 views

Prove that class of regular languages is closed on operation

Let's have an operation $$\odot(L)=\{w\in L \; | \; |w|=2k \land k>0\}$$Show that result of this operation will be regular. PS: It's not homework, it's from last year's exam.
1
vote
1answer
96 views

Prove the following language is not regular

The set of strings of 0's and 1's, beginning with a 1, such that when interpreted as an integer, that integer is prime. I'm assuming the best way to move forward is to use the pumping lemma. I'm ...
0
votes
1answer
119 views

Construction of Regular Expression

I have the problem of needing to construct a regular expression corresponding to the set of strings of 0's and 1's whose number of 0's is divisible by five and whose number of 1's is even. ...
0
votes
1answer
186 views

Prove regular language closed under min and max

Given some regular language $L$, show that $L$ is closed under the following operations: $$\begin{align*} \min(L) &= \{w\mid w\in L,\text{ but no prefix of }w\text{ is in }L \}\\ \max(L) &= ...
1
vote
1answer
131 views

If A ≤ B and A is regular, does that imply that B is regular?

In this question, I want to know what the symbol ≤ means. If it denotes reducible, what is the relationship between reduction and regular language? Or, I need an example to illustrate this ...
0
votes
1answer
87 views

Show: The set of all languages in which every word has odd length contains non-regular languages.

Prove that $\xi = \text{The set of all languages in which every word has odd length}$ over $\Sigma = \{a,b\}$ contains non-regular languages. So I offered this proof and I really think that it ...
0
votes
2answers
85 views

Proving that a regular expression belongs to a certain language

I've often come by questions that require proving that a certain regular expression belongs to that language. Example: Given $\Sigma = \{0,1\}$, and the language $L$ of all the words that have ...
1
vote
1answer
142 views

Proving that $L= \{a^nb^n, n\ge 0\}$ is not a regular language.

The questions i'm 'stuck' on is: Let $\Sigma = \{0,1,2\}$ be the alphabet, and let $L$ be the collection of all the languages that contains only words that have even length. Prove that there are ...
0
votes
2answers
35 views

Subset of A Regular Language

I need to show that a subset of a regular language is regular or not. I think it may not be regular but I could not find a counter example. Do you have any simple example to prove that? Thanks in ...
1
vote
1answer
28 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
2answers
53 views

Can one prove that a language is regular without having a regular expression?

I was wondering if one could prove that a language is regular without showing a DFA/NFA or a regular expression that expresses it. For example: $L = \{w \in \Sigma^* : w \text{ has at least two ...
0
votes
2answers
23 views

Regular Language Operation

I need to show that the given regular language is closed under the following operation. For example: AllSuffixes(L) = {v : uv in L for some u in (0+1)* } I do not ...
0
votes
2answers
86 views

If given a regular language, how can we prove that a sub-language is regular?

This question has been quite confusing me. $\sum = \{a,b,c\}, L \text{ is a regular language}$ and we have to prove that $L^{'} = \{w \in L : w\text{ containts at least one c} \}$ is regular. What ...
1
vote
2answers
50 views

Is $\{w \in \Sigma ^* : |w|_2 mod 4 = 2\}$ a regular language?

Given alphabet $\Sigma = \{1,2,3\}$, is $\{w \in \Sigma^* : |w|_2 \bmod 4 = 2\}$ a regular language? I tried so hard on finding a regular expression but couldn't...
0
votes
1answer
110 views

When does infinite intersection preserve a closed property?

There are two statements well known in Math and Computer Science: Intersection of infinite number of regular languages is not regular. Intersection of infinite number of convex sets is convex. ...
0
votes
1answer
204 views

Show that a language is not regular using Myhill-Nerode Theorem

I'd like to show that the language below is not regular using Myhill-Nerode Theorem. How can I do that? Let Σ = {0, 1}. Let L = {ww|w ∈ Σ*} I am not sure where ...
0
votes
1answer
36 views

$L$ is a class of languages that cannot be represented by a regular expression. How to state cardinality of $L$.

$L$ is a class of languages that cannot be represented by a regular expression. The book says that the cardinality of $L$ is $2^{\aleph_0} > \aleph_0$ what's the logic behind getting the ...
2
votes
1answer
29 views

Regarding regular expression. why do the following strings not exist in the expression.

Let L be the language defined by the regular expression: (a U b U c)((ab U ac U b)*(a U b) U (aa)*) the answer book says that 'aaaa' and 'aaaaaa' do not belong to L. I can show that aaaa and aaaaaa ...
1
vote
1answer
41 views

set of all reg exp vs set of all languages

$\Sigma$ = {a,b,c,d,e} V = {A,B,C,D,E,F,G,H} According to the notes: The set of all regular expressions over $\Sigma$ is infinite and countable. The set of all languages over $\Sigma$ is infinite ...
0
votes
1answer
36 views

Is this language regular ? [automata]

Is this a regular language : $$L = \{w : w \in \{a,b\}^*\text{ and }abw = wba\}$$ Does my automata only need to start with $a$ and $b$, then loop on $a,b$ and finish with $b\to a$, or do I don't ...
0
votes
2answers
41 views

Let $L$ be the language defined by the regular expression $(a \vee b \vee c)(a \vee b \vee c)$

1) How does $|L| = 9$? 2) $|L^*| = \aleph_0$? Thank you
0
votes
1answer
34 views

The pumping theorem and regular language

I have this problem: $L_0 = L(a^*bba^*)$, the language of the regular expression $a^*bba^*$ $L_1 = \{uu \mid u \in L_0 \}$ Is $L_1$ a regular language? I know that I should use the pumping ...
0
votes
2answers
102 views

Pumping Lemma to show a language is not regular

Let $\Sigma = \{a, b\}$. Use the Pumping Lemma to show that $\mathcal L = \{ a^pab^q: p < q \}$ is not regular. Not sure how to apply PL here, if someone can give some direction.
0
votes
0answers
18 views

How to say “Take result X from the following simultanious calculation and multiply by z” in one equation?

If I have a simulataneious equation, for example: { 5x+10y=3 10x+5y=4 } so the person solving the exuation would need to calculate X and Y (1/3 and 2/15 ...
1
vote
1answer
33 views

Post-concatenation of the languages represented by the null set

I have a small question regarding concatenation of regular languages: Is it true that the concatenation $L\varnothing$, where $L$ is any regular language, result in $\varnothing$? Namely, does ...
0
votes
2answers
38 views

Are those two regular languages the same?

Given an alphabet of {a,b} where Na denotes the number of occurrences of a, and Nb the number of occurrences of b: ...
1
vote
1answer
106 views

Pumping lemma $L=\{a^ib^j | i \neq j ; i,j \ge 0\}$ [duplicate]

So, let's have language $L=\{a^ib^j | i \neq j ; i,j \ge 0\}$ I have to prove that it's not regular. \begin{align} \omega=a^nb^{n+1}=a^{n-1}ab^{n+1} \end{align} \begin{align} x&=a^k\\ y&=a\\ ...
1
vote
2answers
97 views

interpreting language for finite state machine

Can someone explain to me what this means in clear english and maybe give me a hint for how to make a NDFSM (non-deterministic finite state machine) that accepts this language? I understand that the 3 ...
0
votes
1answer
67 views

Constructing a parallel composition from a given transition system and automaton

I am looking at an exercise, where it asks me to construct a parallel composition from a given transition system and an automaton. The transition system looks like this: and the automaton (with ...
4
votes
2answers
112 views

Number of states required to recognize $\{ ss : s \in \{ 0 , 1 \}^*, |s| = i \}$ and its complement

$$\Sigma = \{0,1\}\;\\ S_{i} = \left\{ss: s\in {\Sigma}^{*} \text{and $s$ has length $i$}\right\}$$ Prove that for any $i$, any DFA recognizing $S_{i}$ must have $2^{i}$ or more states. Design a ...
10
votes
2answers
101 views

Mystery Men Movie - Propositional Logic

In the movie Mystery Men, there is this scene: Captain Amazing (good guy): I knew you couldn't change. Casanova Frankenstein (bad guy): I knew you'd know that. Captain Amazing: Oh, I know. And ...
2
votes
1answer
124 views

A variation on counting Balanced Brackets

While counting the number of balanced bracket expressions of length $2n$, the constraint is that for every prefix substring: $$\text{[number of occurrences of (]} - \text{[number of occurrences of )]} ...
0
votes
1answer
227 views

Does closure under the union and concatenation operations imply closure under the star operation?

Given any two languages $A$ and $B$, recall the following regular operations: Union: $A \cup B = \{x \mid x \in A \text{ or } x \in B\}$ Concatenation: $A \circ B = \{xy \mid x \in A \text{ ...
1
vote
2answers
284 views

Constructing a finite automata from a subset of its language

I am attempting to solve the following problem: Let $M=(Q,\Sigma,\delta,q_0,F)$ be a deterministic finite automata which accepts $L(M)$, and let $E$ be the subset of $L(M)$ consisting of all words of ...
1
vote
2answers
65 views

The Relation of Cellular Automata to Languages

In Conway's Game of Life, would a cell be considered a deterministic finite automata? Is there a language for the automata, and would it be a regular language? In probabilistic cellular automata, are ...
0
votes
1answer
47 views

Connection of closed subsets of $A^{\omega}$ and deterministic Büchi-Automata, Question from Book: Infinite Word by D. Perrin & J.-E. Pin

In the Book Infinite Words (homepage) it is proofed that: If $X \subseteq A^{\omega}$, then regarding the Cantor-Topology, the following is equivalent: (1) $X$ is closed (2) $X$ is recognized by a ...
1
vote
1answer
54 views

Is there an (explicit?) bijection from the set of all automatons to the set of all regular expressions that conserves the recongnised language

Let $\Sigma$ be an alphabet, $R$ be the set of regular expressions on $\Sigma$ (that is, trees with leave's values in $\left\{\varepsilon\right\}\cup \Sigma$ and three types of interior nodes, one ...
0
votes
1answer
142 views

Question on NP and its closure properties

Is this true or false? If $L_1$∈ NP and $L_2$∈ NP, then $L_1$∩ $L_2$ ∈ NP. NP = nondeterministic polynomial
1
vote
2answers
62 views

Trying to describe this Turing Machine

Let's say I have the following turing machine: $F_n$ = {M | M is a TM and |L(M) ≤ n} In english, for some given natural number n, $F_n$ is the language of all turing machines that accept no more ...
0
votes
1answer
69 views

Need help with this regular language proof

I'm trying to prove that if $L$ is regular, then $L_S$ is regular as well. $L_s$ = {$x$ | $∃$ $w ∈ Σ^*$ such that $wx∈L$} I know one way to do this would be to create an NFA that accepts $L$, then ...
2
votes
0answers
48 views

Expressiveness of finite memory programs

Assume we have a simple programming language with while, if, := (assignment), ...