Recent questions tagged proof

0 votes

0 answers

1

Michael Sipser Edition 3 Exercise 2 Question 52 (Page No. 159)
Show that every DCFG generates a prefix-free language.

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 2 views

0 votes

0 answers

2

Michael Sipser Edition 3 Exercise 2 Question 51 (Page No. 159)
Show that every DCFG is an unambiguous CFG.

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 1 view

0 votes

0 answers

3

Michael Sipser Edition 3 Exercise 2 Question 46 (Page No. 158)
Consider the following CFG $G:$ $S \rightarrow SS \mid T$ $T \rightarrow aT b \mid ab$ Describe $L(G)$ and show that $G$ is ambiguous. Give an unambiguous grammar $H$ where $L(H) = L(G)$ and sketch a proof that $H$ is unambiguous.

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 4 views

0 votes

0 answers

4

Michael Sipser Edition 3 Exercise 2 Question 45 (Page No. 158)
Let $A = \{wtw^{R}\mid w,t\in\{0,1\}^{\ast}\:\text{and} \mid w \mid = \mid t \mid \}$. Prove that $A$ is not a CFL.

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 1 view

0 votes

0 answers

5

Michael Sipser Edition 3 Exercise 2 Question 44 (Page No. 158)
If $A$ and $B$ are languages, define $A \diamond B = \{xy \mid x \in A\: \text{and}\: y \in B \;\text{and} \mid x \mid = \mid y \mid \}$. Show that if $A$ and $B$ are regular languages, then $A \diamond B$ is a CFL.

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 3 views

0 votes

0 answers

6

Michael Sipser Edition 3 Exercise 2 Question 43 (Page No. 158)
For strings $w4 and $t,4 write $w \circeq t$ if the symbols of $w$ are a permutation of the symbols of $t.$ In other words, $w \circeq t$ if $t$ ... a regular language is context free. What happens in part $(a)$ if $\Sigma$ contains three or more symbols? Prove your answer.

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 1 view

0 votes

0 answers

7

Michael Sipser Edition 3 Exercise 2 Question 42 (Page No. 158)
Let $Y = \{w\mid w = t_{1}\#t_{2}\#\dots t_{k} \:\text{for}\: k\geq 0,\text{each}\: t_{i}\in 1^{\ast}, \text{and}\: t_{i}\neq t_{j} \text{whenever}\: i\neq j\}$.Here $\Sigma = \{1,\#\}$. Prove that $Y$ is not context free.

asked 1 day ago in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 1 view

0 votes

0 answers

8

Peter Linz Edition 4 Exercise 8.1 Question 8 (Page No. 212)
Determine whether or not the following languages are context-free. (a) $L=$ {$a^nww^Ra^n : n ≥ 0, w ∈$ {$a,b$}*} (b) $L=$ {$a^nb^ja^nb^j : n ≥ 0, j ≥ 0$}. (C) $L=$ {$a^nb^ja^jb^n : n ≥ 0, j ≥ 0$}. (d) $L=$ {$a^nb^ja^kb^l : n + j ≤ k + l$ ... $ L=$ {$a^nb^nc^j : n ≤j$}. (g) $L=$ {$w ∈$ {$a, b, c$}* $: n_a(w)= n_b (w)=2n_c(w)$}.

asked Jun 25 in Theory of Computation by Naveen Kumar 3 Boss (14.9k points) | 59 views

0 votes

1 answer

9

Michael Sipser Edition 3 Exercise 2 Question 36 (Page No. 158)
Give an example of a language that is not context free but that acts like a $CFL$ in the pumping lemma$.$ Prove that your example works$.$ $\text{(See the analogous example for regular languages in Question 54.)}$

asked May 4 in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 53 views

0 votes

1 answer

10

Michael Sipser Edition 3 Exercise 2 Question 35 (Page No. 157)
Let $G$ be a $CFG$ in Chomsky normal form that contains $b$ variables$.$ Show that if $G$ generates some string with a derivation having at least $2^{b}$ steps$, L(G)$ is infinite$.$

asked May 4 in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 29 views

0 votes

1 answer

11

Michael Sipser Edition 3 Exercise 2 Question 34 (Page No. 157)
Let $G = (V, \Sigma, R, S)$ be the following grammar. $V = \{S, T, U\}; \Sigma = \{0, \#\};$ and $R$ is the set of rules$:$ $S\rightarrow TT\mid U$ $T\rightarrow 0T\mid T0\mid \#$ ... existence of a pumping length $p$ for $B.$ What is the minimum value of $p$ that works in the pumping lemma$?$ Justify your answer$.$

asked May 4 in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 65 views

0 votes

2 answers

12

Michael Sipser Edition 3 Exercise 2 Question 32 (Page No. 157)
Let $\Sigma = \{1, 2, 3, 4\}$ and $C = \{w\in\Sigma^{*}\mid$ $\text{in $w$, the number of $1's$ equals the number of $2's,$ and the number of $3's$ equals the number of }$4's\}.$ Show that $C$ is not context free$.$

asked May 4 in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 50 views

+1 vote

1 answer

13

Michael Sipser Edition 3 Exercise 2 Question 26 (Page No. 157)
Show that if $G$ is a $CFG$ in Chomsky normal form$,$ then for any string $w\in L(G)$ of length $n\geq 1,$ exactly $2n − 1$ steps are required for any derivation of $w.$

asked May 4 in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 25 views

0 votes

0 answers

14

Michael Sipser Edition 3 Exercise 2 Question 25 (Page No. 157)
For any language $A,$ let $SUFFIX(A) = \{v\mid uv \in A$ $\text{for some string u\}}.$ Show that the class of context-free languages is closed under the $\text{SUFFIX operation.}$

asked May 4 in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 22 views

0 votes

1 answer

15

Michael Sipser Edition 3 Exercise 2 Question 24 (Page No. 157)
Let $E=\{a^{i}b^{j}\mid i\neq j$ $\text{and}$ $2i\neq j\}.$ Show that $E$ is a context-free language$.$

asked May 4 in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 22 views

0 votes

0 answers

16

Michael Sipser Edition 3 Exercise 2 Question 23 (Page No. 157)
Let $D = \{xy\mid x, y\in \{0,1\}^{*}$ $\text{and}$ $\mid x\mid = \mid y\mid$ $\text{but}$ $x\neq y\}.$ Show that $D$ is a context-free language$.$

asked May 4 in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 21 views

0 votes

0 answers

17

Michael Sipser Edition 3 Exercise 1 Question 73 (Page No. 93)
Let $\sum = \{0,1, \#\}.$ Let $C = \{x\#x^{R}\#x| x\in\{0,1\}^{*}\}.$Show that $\overline{C}$ is a $\text{CFL}.$

asked Apr 30 in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 15 views

0 votes

0 answers

18

Michael Sipser Edition 3 Exercise 1 Question 72 (Page No. 93)
Let $M_{1}$ and $M_{2}$ be $\text{DFA's}$ that have $k_{1}$ and $k_{2}$ states, respectively, and then let $U = L(M_{1})\cup L(M_{2}).$ Show that if $U\neq\phi$ then $U$ contains some string $s,$ where $|s| < max(k1, k2).$ Show that if $U\neq\sum^{*},$ then $U$ excludes some string $s,$ where $|s| < k1k2.$

asked Apr 30 in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 48 views

0 votes

1 answer

19

Michael Sipser Edition 3 Exercise 1 Question 71 (Page No. 93)
Let $\sum = \{0,1\}$ Let $A=\{0^{k}u0^{k}|k\geq 1$ $\text{and}$ $u\in \sum^{*}\}.$ Show that $A$ is regular. Let $B=\{0^{k}1u0^{k}|k\geq 1$ $\text{and}$ $u\in \sum^{*}\}.$Show that $B$ is not regular.

asked Apr 30 in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 29 views

0 votes

1 answer

20

Michael Sipser Edition 3 Exercise 1 Question 70 (Page No. 93)
We define the $\text{avoids}$ operation for languages $A$ and $B$ to be $\text{A avoids B = {w| w ∈ A and w doesn’t contain any string in B as a substring}.}$ Prove that the class of regular languages is closed under the ${avoids}$ operation.

asked Apr 30 in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 21 views

0 votes

0 answers

21

Michael Sipser Edition 3 Exercise 1 Question 69 (Page No. 93)
Let $\sum=\{0,1\}.$ Let $WW_{k}=\{ww|w\in \sum^{*}$ and $w$ is of length $k\}.$ Show that for each $k,$ no DFA can recognize $WW_{k}$ with fewer than $2^{k}$ states. Describe a much smaller $NFA$ for $\overline{WW_{k}},$ the complement of $WW_{k}.$

asked Apr 30 in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 18 views

0 votes

0 answers

22

Michael Sipser Edition 3 Exercise 1 Question 68 (Page No. 93)
In the traditional method for cutting a deck of playing cards, the deck is arbitrarily split two parts, which are exchanged beforereassembling the deck. In a more complex cut, called $\text{Scarne's cut,}$ the deck is broken into three parts ... $ CUT(CUT(B)).}$ Show that the class of regular languages is closed under $\text{CUT}.$

asked Apr 30 in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 35 views

0 votes

0 answers

23

Michael Sipser Edition 3 Exercise 1 Question 61 (Page No. 92)
Let $Σ = \{a, b\}.$ For each $k\geq 1,$ let $C_{k}$ be the language consisting of all strings that contain an a exactly $k$ places from the right-hand end$.$ Thus $C_{k}=\sum^{*}a\sum^{k-1}.$ Prove that for each $k,$ $\text{no DFA}$ can recognize $C_{k}$ with fewer than $2^{k}$ states.

asked Apr 30 in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 11 views

0 votes

0 answers

24

Michael Sipser Edition 3 Exercise 1 Question 58 (Page No. 92)
If $A$ is any language,let $A_{\frac{1}{2}-\frac{1}{3}}$ be the set of all strings in $A$ with their ,middle thirds removed so that $A_{\frac{1}{2}-\frac{1}{3}}=\{\text{xz|for some y,|x|=|y|=|z| and xyz $\in$ A\}}.$ Show that if $A$ is regular,then $A_{\frac{1}{2}-\frac{1}{3}}$ is not necessarily regular.

asked Apr 30 in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 7 views

0 votes

0 answers

25

Michael Sipser Edition 3 Exercise 1 Question 57 (Page No. 92)
If $A$ is any language,let $A_{\frac{1}{2}-}$ be the set of all first halves of strings in $A$ so that $A_{\frac{1}{2}-}=\{\text{x|for some y,|x|=|y| and xy $\in$ A\}}.$ Show that if $A$ is regular,then so is $A_{\frac{1}{2}-}.$

asked Apr 30 in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 19 views

0 votes

0 answers

26

Michael Sipser Edition 3 Exercise 1 Question 56 (Page No. 91)
If $A$ is a set of natural numbers and $k$ is a natural number greater than $1,$ let $B_{k}(A)=\{\text{w| w is the representation in base k of some number in A\}}.$ Here, we do not allow leading $0's$ in the representation of a ... a set $A$ for which $B_{2}(A)$ is regular but $B_{3}(A)$ is not regular$.$ Prove that your example works.

asked Apr 30 in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 27 views

0 votes

1 answer

27

Michael Sipser Edition 3 Exercise 1 Question 55 (Page No. 91)
The pumping lemma says that every regular language has a pumping length $p,$ such that every string in the language can be pumped if it has length $p$ or more. If $p$ is a pumping length for language $A,$ so is any length $p^{'}\geq p.$ The minimum pumping ... $\epsilon$ $1^{*}01^{*}01^{*}$ $10(11^{*}0)^{*}0$ $1011$ $\sum^{*}$

asked Apr 30 in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 33 views

0 votes

1 answer

28

Michael Sipser Edition 3 Exercise 1 Question 54 (Page No. 91)
Consider the language $F=\{a^{i}b^{j}c^{k}|i,j,k\geq 0$ $\text{and if}$ $ i = 1$ $\text{then} $ $ j=k\}.$ Show that $F$ is not regular. Show that $F$ acts like a regular language in the pumping lemma. ... three conditions of the pumping lemma for this value of $p.$ Explain why parts $(a)$ and $(b)$ do not contradict the pumping lemma.

asked Apr 30 in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 45 views

0 votes

0 answers

29

Michael Sipser Edition 3 Exercise 1 Question 53 (Page No. 91)
Let $\sum=\{0,1,+,=\}$ and $ADD=\{x=y+z|x,y,z$ $\text{are binary integers,and}$ $x$ $\text{is the sum of}$ $y$ $\text{and}$ $z\}.$ Show that $\text{ADD}$ is not a regular.

asked Apr 30 in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 10 views

0 votes

0 answers

30

Michael Sipser Edition 3 Exercise 1 Question 52 (Page No. 91)
$\text{Myhill-Nerode theorem.}$ Refer to $\text{Question 51}.$Let $L$ be a language and let $X$ be a set of strings. Say that $X$ is $\text{pairwise distinguishable}$ by $L$ if every two distinct strings in $X$ are ... $\text{DFA}$ recognizing it$.$

asked Apr 30 in Theory of Computation by Lakshman Patel RJIT Veteran (50.8k points) | 11 views

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true

Recent questions tagged proof

Recent Posts

Recent Blog Comments