The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
2answers
16 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 ...
0
votes
0answers
39 views

Proving languages are undecidable

Let L5 be the language { {G,D} | G is a CFG, D is a DFA, and L(D) ⊆ L(G) } Show that L5 is undecidable. Is L5 R.E.? Is it co-R.E.? I am not quite sure where exactly to start with this. Could ...
2
votes
3answers
34 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 ...
1
vote
1answer
18 views

Equivalence classes in a regular language

Question: Let L be a regular language, ~${_L}$ is it's equivalence relation (as was defined in Myhill Nerode theorem) that divides $\Sigma^* $ to 4 non empty equivalence classes A1, A2,A3,A4. Let ...
0
votes
1answer
10 views

Formal languages problem

What is meant by L1L2 ? Does the n have to be the same for both? So, aabbcc is an element of L1L2 and aabbcccc is not? How about the first problem - Epsilon. Is it an element of L1L2? Since n>0 in L1 ...
0
votes
1answer
55 views

Is this a regular language ? SubString(L1, L2) = {w | ∃x, y ∈ L1, xwy ∈ L2}

Question: Define the following operation: SubString(L1, L2) = {w | ∃x, y ∈ L1, xwy ∈ L2} Let L1 be any language, and L2 regular. Prove that SubString(L1, L2) is regular. Thoughts: I need to somehow ...
0
votes
1answer
15 views

Designing a Pushdown Automation to accept a language

Im a novice trying to understand the theory of computation.Im trtying to learn about PDA.I understand that it is a machine counterpart of CFG.Im basically referring to Introduction to Automata Theory ...
1
vote
1answer
20 views

Automata Language regularity proof by construction.

I've been trying to prove or disprove a question that popped during our last session in Uni, we've been using automaton constructing to prove regularity for a while now and I really do have the handle ...
0
votes
0answers
11 views

Conjunction and XOR of Regular Language to DFA

If you could help me with this homework it would be greatly appreciated. If we assume that $M(i)$ is the finite automaton that recognises the regular language $L(i)$ for $i = 1,2,\ldots,n$, how can I ...
0
votes
2answers
30 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 ...
0
votes
1answer
20 views

How to construct a context free grammar that generate following language. $\{a^nb^nc^k \in \{a,b,c\}^* | n,k >= 0\} $

$$\{a^nb^nc^k \in \{a,b,c\}^* | n,k >= 0\} $$ $E \to aEbS $ $S \to c$ I do not know where to go next, or even if this is right at all?
0
votes
1answer
22 views

is $\{a^n b^m | n \neq m\} $regular or non regular?

$\left\{a^nb^m\mid n \neq m \right\}\subset \{a, b\}$. I have been asked to prove this is irregular but I think it is regular as I can write a regular expression a*b* for it. Am I wrong? If so how ...
0
votes
1answer
28 views

Construct context free grammar which generates following language $\{wcw^R\in\{a, b, c\}^*\mid w\in\{a, b, c\}^* \}$

(i) $\{wcw^R\in\{a, b, c\}^*\mid w\in\{a, b, c\}^* \}$ So far I have $E \to EcE$ $E \to a$ $E \to b$ $E \to c$ But I'm new at this and feel I'm miles away from a finished answer
0
votes
2answers
35 views

If language L is not regular, and L ⊂ M. Do we know if M is regular or not?

I have been given some questions to do regarding regular/irregular languages. And have the following questions True/False (i) If L is not regular and L ⊂ M, then M is not regular. (ii) If L ⊂ M and ...
1
vote
1answer
39 views

{w| w ∈ {a, b} * is not a palindrome} Prove this language is not regular. [duplicate]

I've been doing some work to prove some languages are not regular. I have previously used pumping lemma to prove by contradiction. However I am used to questions which ask to prove languages such as ...
0
votes
3answers
40 views

How can I prove this language is not regular?

$$\left\{a^{2^n}\mid n \ge 0\right\} \subset \{a\}^*$$ How can I prove this language is not regular?
-1
votes
1answer
37 views

Regular expression with xor [duplicate]

Can anyone help me with this question: I know i asked a similar question not a while ago but i'm not able to understand how its possible. If anyone could give me a lot of examples instead of an ...
0
votes
1answer
20 views

Regular expression problem

I have this question and no clue how to solve. Thanks for your help I need to build the regular expression matching this language $$L=\{ 0^m~1^n | (m+n) \pmod 3 = 1 \}$$
1
vote
0answers
20 views

Help with proving a language is regular (Sipser problem 1.49a)

I am working through Sipser's Introduction to the theory of computation on my own, so I don't have access to a teacher. Hopefully you can help me! Giving hints is highly appreciated. This question is ...
0
votes
0answers
18 views

Proving regular languages over an alphabet

Language L over alphabet Σ THREE(L) = {abc | a,b,c ∈ Σ and ∃x ∈ Σ∗ s.t. abcx ∈ L} and every String in THREE(L) is exactly 3 characters long I am not sure how to prove that L whenever L is a regular ...
0
votes
0answers
23 views

Proving regular languages

I am having a bit of trouble understand this. Q. Define the lnaguage HASPREFIX(L) = {xy | x , y ∈ Σ*, x ∈ L, xy ∈ L, and |y| >/= 0} Prove that whenever L is a regular language so is HASPREFIX(L) ...
0
votes
0answers
76 views

Prove that whenever L is a regular language so is HasPrefix(L)

For a language $L$ over an alphabet $\Sigma$, define the language $\operatorname{HasPrefix}(L)$ as follows: $$\operatorname{HasPrefix}(L) = \{xy\mid x,y \in\Sigma^*, x \in L, xy \in L, |y|> 0\}$$ ...
1
vote
1answer
51 views

How to prove that a language `L` is not a regular language?

Given the following question: Prove that the following language is not a regular language: A language L in alphabet $\Sigma = \{a, b\}$ where every word ...
0
votes
0answers
26 views

How to explain if such a language is regular?

Could some one explain to me whether the following languages $$L_1 = \{a^nb^n\mid n\geq 0\},\;\;\;\;L_2 = \{a,b\}^*$$ are regular or not?
0
votes
0answers
17 views

Constructing a nondeterministic automaton from deterministic

Construct a nondeterministic finite-state automaton that recognizes the language generated by the regular grammar G = {V,T,S,P} where V = {0,1,S,A,B}, T = {0,1}, S is the start symbol, and the set of ...
1
vote
0answers
33 views

Is this correct way to prove that { $uv$ $\mid$ $u$ and $v$ are strings over $(0,1)$ & $|u| = |v|$ } language is not regular?

I proved this using Pumping Lemma in the following way, Taking $p$ as pumping length then let us take a string $S$ where, $|u| = |v| = p$ Now according to pumping lemma $S$ can be split into three ...
0
votes
1answer
61 views

How to prove that $ \{ 0^n 1^{5n} : n \ge 10000 \} $ is not a regular language?

I proved that $$ \{0^n 1^{5n} : n \ge 0\} $$ is not a regular language using Pumping Lemma by following way. Solve by contradiction that $ L = \{ 0^n 1^{5n} : n >= 0 \}$ is regular language. ...
0
votes
1answer
17 views

If $R$ is a regular language and both $L - R$ and $L ∩ R$ are context-free then $L$ is context-free

If $R$ is a regular language and both $L - R$ and $L ∩ R$ are context-free then $L$ is context-free I have to prove or give a counterexample. I know the closures properties of CFL, however, this ...
1
vote
1answer
33 views

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

I saw that similar questions have been answered on this site, but I've been unable to translate those answers to my problem. $$L=\{ww^R\mid w \in \{a,b\}^*\}$$ This is what I tried: BWOC, assume ...
0
votes
1answer
46 views

Question about formal languages, quotient operator L1/L2.

I come across this problem: Consider the following regular languages: L1={a*b*c*} over the alphabet A={a,b,c} L2={( a b | b b | a )*} the alphabet is the same as above. Find the shortest strings ...
1
vote
1answer
21 views

Prove regular languages closed under operation by changing alphabet?

Suppose we have the following language operation: $Duplicate(L) = \{Duplicate(w)|w \in L\}$ where if $w=w_1w_2\ldots w_n$ $Duplicate(w) = w_1w_1w_2w_2 \ldots w_nw_n$. It is simple to construct a DFA ...
0
votes
1answer
27 views

Is this language regular? $\{0^n 1^m \mid m \ne n\}$, I don't understand the direct proof by pumping length

There is a direct way to prove it: If $p$ is the pumping length and we take the string $s = 0^{(p)}1^{(p+p!)}$, then no matter what the decomposition $s = xyz$ is the string $xy^{(1+p!/|y|)}z$ will ...
0
votes
1answer
29 views

Pumping Lemma for a regular language

I've done pumping lemma proofs in the past but I'm honestly not even sure where to start on this problem. Using the Pumping Lemma for Regular Languages show that the language $$L = \{a^i b^j c^k ...
0
votes
1answer
30 views

I don't understand the value of the following regular expressions.

$$\begin{align} 0^{*}10^{*} &= \{w ~\mid ~ w \text{ contains a single } 1\} \\ \Sigma^{*}1\Sigma^{*} &= \{w ~\mid ~w \text{ has at least one } 1\} \\ 0 \Sigma^{*}0~\cup ~1\Sigma^{*}1~\cup ...
3
votes
1answer
137 views

Challenge on Some Language and PDA

Suppose We have Some language as follows: $L_1=\{w^* | w=x \text{ and } x \in \Sigma^*\}$ $L_2=\{ww^R ww^R | w \in ( \Sigma + \Sigma)^*\}$ $L_3=\{w | w=xy, x,y \in \Sigma^*, y \text{ is a ...
0
votes
1answer
27 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
18 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? ...
1
vote
1answer
39 views

Regular language that has a string that cannot be pumped.

This is a question from a past exam. Consider the language $F = \{w | w \in 0^{*}1^{*}\}$ that is kown to be regular. a) Show that if string $w$ is chosen to be $0^p1^p$, that is a member ...
1
vote
0answers
24 views

Nonregular languages that satisfy the pumping lemma at different strengths

There are three versions of the pumping lemma that I've seen, each one stronger than the last (as in it fails on some non-regular languages that pass the weaker ones) The three versions are as ...
0
votes
1answer
47 views

equivalence class for language in Theory of automata

we say x,y is equivalent to language L, if for any $z \in L$ we have: $xz \in L \Longleftrightarrow yz \in L$. for $ L= (ab \cup aab)^* $, what is the equivalence class for L? my professor ...
1
vote
1answer
71 views

disprove $L = \{ a^nb^n\mid n \geq 0 \}$ is not a context-free using pumping lemma for CFL

I am writing something about pumping Lemma. I know that the language $L = \{ a^nb^n\mid n \geq 0 \}$ is context-free. But I don't understand how this language satisfies the conditions of pumping lemma ...
0
votes
0answers
15 views

Origin of the stable distribution name

Mandelbrot (1963) claimed the name stable distribution comes from Paul Levy work: "...The purpose of this paper will be to present and test such a new model of price behavior in speculative markets. ...
-2
votes
1answer
45 views

CFG with reverse strings

I've been trying to figure this out for a while, and I'm at a total loss: Write a context-free grammar that generates the language $\{x y\ |\ x$ is a string over $\{a,b,c\},\ y$ is a reverse of ...
2
votes
1answer
26 views

Why is $\left\{a\right\}^*\cap L(A)=\emptyset$? where $\delta(q,a)=q$

I am trying to solve this particular problem from Automata Theory by Ullman, Hopcroft, it is as shown below : Let $A$ be a $DFA$ and $a$ be a particular input symbol of $A$, such that for all states ...
0
votes
1answer
25 views

find a regular expression

find a regular expression for w such that it does not contain $ aab $ , where w is the strings of $a$'s and $b$'s . ans: I know how to draw the same question with $ aab $ , but cant understand how to ...
0
votes
0answers
36 views

contradiction of pumping lemma on even palidrome language's completion

I have the language of all the words that are not even length palindromes, or more formally: $L= \{ w: \forall u\in\Sigma^*, w\ne uu^r \}$. And I need to prove that the Pumping Lemma for regular ...
0
votes
2answers
21 views

Regular Expression Similarity Check

I was solving Formal Language and Automata Theory for a competitive exam, whence I came upon this following question: The regular expression 0*(10*)* denotes same set as: 0(0+10)* (0+1)10(0+1) ...
1
vote
1answer
9 views

Find a state machine or a regex that accept the following language description

The alphabet of the language L is {a, b} and there has to be an even number of both a's and b's but no other restrictions apply. I've been at this for over an hour, drawing state machines that lead ...
2
votes
3answers
103 views

Show that the language is not regular using the pumping lemma.

I have to show that the language $L = \{ a^k b^k \mid k > 0 \}$ is not regular using the pumping lemma. I have done the following: Let $i \geq 1$ $$x = a^i b^i \in L$$ $$|x| = 2i \geq i $$ ...
0
votes
1answer
24 views

Check if it is regular language

I have a language $L = \{ a^i b^j c^k \mid i \geq 1 \land j \geq 1 \land k \geq 1 \land (i \neq j \lor j \neq k) \}$ and how to check if it is regular language? I tried using pumping lemma for ...