# Tagged Questions

22 views

### PDA and Some language Grammar inference

L1={$w^*$| w=x and $x \in \Sigma^*$} L2={$ww^R ww^R$| $w \in ( \Sigma + \Sigma)^*$} L3={$w | w=xy, x,y \in \Sigma^*$, y is a substring of x} a) there is a PDA(push down automata) that accept ...
43 views

### Regular Language and Unknown Operation

I read the $L$ is a Regular language. Define $L'$ as following: $$L'=\{a_2a_1a_4a_3\ldots a_{2n}a_{2n-1}\mid a_1a_2\ldots a_{2n} \in L\}.$$ why $L'$ is Regular? any hint or idea would be highly ...
36 views

### A CFG Grammar for One Language

Suppose : $w_1,w_2 \in \{a,b\}^∗$ and $L=\{w_1w_2 \mid w_1,w_2 \in \{a,b\}^* \land n_a(w_1)=n_b(w_2)\}$ $n_a$ is number of $a$'s and $n_b$ is number of $b$'s. This is a Entrance Exam question. I ...
58 views

### Challenge on Property of Complement in Language

We have: and M be a finite automata. Suppose d(M) be a deterministic automata that equivalence to M. if $M_1$ and $M_2$ be two finite automata, $M_1 + M_2$ is the finite automata such that the ...
27 views

22 views

### How can I show ithat a language is regular?

I have a very quick question about regular languages, I think $\{a^{2n}| n\geq 1\}$ is regular. I do know that pumping lemma can be used to show something that is not regular. I am wondering what ...
27 views

### Question About Pumping Lemma used on a FA

I am learning about pumping lemma and I am trying to solve a problem. I need to use pumping lemma to show that: the Language L(M) defined by the following machine is infinite. Here is the dfa: ...
52 views

### This proof in my textbook involving the pumping lemma appears incorrect - is it?

It states Let $B$ be the language $\{0^n1^n2^n | n \geq 0\}$. We use the pumping lemma to prove that $B$ is not regular. The proof is by contradiction. Assume to the contrary that $B$ is regular. ...
71 views

### Is $L = \{(x,y,z) | x+y=z\}$ a regular language?

Suppose $x,y,z$ are coded as decimal or their binary representations in an appropriate DFA. Is $L$ regular? My intuition tells me that the answer is no, because there are infinitely many combinations ...
202 views

### Proof of Equivalence of NFA and DFA, quick question about the setup

I am looking at the proof of equivalence of non determinstic finite automata(NFA) and deterministc finite automata(DFA). I am have a small quesion about the construction: Let ...
54 views

### Pumping Lemma for regular languages proof template

http://www.cs.uiuc.edu/class/fa06/cs273/Lectures/pumping-lemma/pumping-lemma.html So, I went to that site and it says: $w = xyz$ $|xy| \leq p$ $|y| \geq 1$ for all $i$, $xy^iz$ is in ...
45 views

### Struggling with Proof Writing. Simple question for demostration.

I am practicing writing proofs over regular expressions. Here is the question: Show that $(r\cup \varepsilon)^*= r^*$, where $r$ is a string. Intuitively, the left hand side is the concatenation of ...
26 views

### Give a regular expression for $A = \{1^{k}y|k \geq 1, y \in \{0,1\}^{*}$ and $y$ contains at least $k$ $1$'s $\}$

The regular expression that is given is $1(0 \cup 1)^{*}10^{*}$. I'm having trouble realizing why this regular expression describes the language given. For example, the string (for $k$ = 4) $1111$ ...
122 views

### Prove the language $\{a^k b^l : k \neq l \}$ is not regular

Prove that the following language is not regular: $$L=\{a^k b^l : k,l \ge0, k\ne l\}$$ The problem is that I should use "distinguished states" not the pumping lemma, which is usually used for such ...
42 views

### A correct proof for this pumping lemma example?

Given the language $L = \{0^{2^n} | n \geq 1\}$ So, the language contains all strings that have $2^n$ $0$s. First of all I take $z = a^{2^p}$ where $p$ is the constant guaranteed by the pumping ...
322 views

### Regular expression and DFA/NFA questions

If a language L is generated by a regular expression, then L is recognized by a DFA. I think this is true, because regular expressions describe regular languages, those of which are exactly ...
92 views

### NFA for $(ab|a)^{*}$ using only 2 states

In Introduction to the Theory of Computation by Michael Sipser, there's an example which shows how to convert the regular expression $(ab|a)^{*}$ into an NFA. The "standard" method results in 8 ...
49 views

### is this language regular or not?

I have problem with this language $$L = \{ a^n b^m : \text{n+m is odd} \}$$ is it regular or not My Solution I used pumping lemma, w = a^2p b^2p+1 (the same for a^2p+1 b^2m ) ...
72 views

### Finding regular expressions

I'm given the DFA shown below and need to find regular expressions for the following languages: $L_{1,2}^0, L_{2,1}^6, L_{2,5}^4, L_{2,3}^5, L_{1,3}^5$. The language $L_{p,q}^r$ is defined as ...
167 views

### DFA for Boolean Formula

Let $f\left( b_{1}, \dots , b_{n} \right)$ be a boolean function. Define $S_{f} = \{\left( b_{1}, \dots , b_{n} \right): f\left( b_{1}, \dots , b_{n} \right)=1; b_{i} \in \{0,1\}, 1\leq i \leq n \}$ ...
### Is the next expression true: $(L_1 \cap L_2 )L_3\subseteq L_1L_3\cap L_2 L_3$?
Let $L_1,L_2,L_3$ be languages, Is the next expression true: $(L_1 \cap L_2 )L_3\subseteq L_1L_3\cap L_2 L_3$? After a half an hour of trying to disprove it, I've decided my intuition might be wrong. ...