Recent questions without an upvoted answer / GATE Overflow for GATE CSE

Let $G_1$ and $G_2$ be grammars with $G_1$ regular. Is the problem $L(G_1) = L(G_2)$ decidable when $\text(a)$ $G_2$ is unrestricted,$\text(b)$ when $G_2$ is context-free...

Rishi yadav

308 views

Rishi yadav asked Mar 16, 2019

0 votes

1 answer

9192

Peter Linz Edition 5 Exercise 12.4 Question 7 (Page No. 321)
Let $G_1$ be a context-free grammar and $G_2$ a regular grammar. Is the problem $L(G_1)\cap L(G_2) = \phi$ decidable$?$

Let $G_1$ be a context-free grammar and $G_2$ a regular grammar. Is the problem $L(G_1)\cap L(G_2) = \phi$ decidable$?$

Rishi yadav

306 views

Rishi yadav asked Mar 16, 2019

0 votes

0 answers

9193

Peter Linz Edition 5 Exercise 12.4 Question 6 (Page No. 321)
Let $M$ be any Turing machine. We can assume without loss of generality that every computation involves an even number of moves. For any such computation $q_0w\vdash x_1\vdash x_2\vdash ...\vdash x_n$, we can then construct the string ... to show that $ L(G) = \Sigma^* $ is undecidable over the domain of all context-free grammars G.

Let $M$ be any Turing machine. We can assume without loss of generality that every computation involves an even number of moves. For any such computation ...

Rishi yadav

209 views

Rishi yadav asked Mar 16, 2019

0 votes

1 answer

9194

Peter Linz Edition 5 Exercise 12.4 Question 5 (Page No. 321)
Let $L_1$ be a regular language and $G$ a context-free grammar. Show that the problem $“L_1 \subseteq L(G)”$ is undecidable.

Let $L_1$ be a regular language and $G$ a context-free grammar. Show that the problem $“L_1 \subseteq L(G)”$ is undecidable.

Rishi yadav

226 views

Rishi yadav asked Mar 16, 2019

0 votes

0 answers

9195

Peter Linz Edition 5 Exercise 12.4 Question 4 (Page No. 321)
$\text{Theorem}:$ There exist no algorithms for deciding whether any given context-free grammar is ambiguous. Show that if the language $L(G_A)\space \cap L(G_B) $ in Theorem is regular, then it must be empty. Use this to show that the problem $“L(G)$ is regular $”$ is undecidable for context-free $G$.

$\text{Theorem}:$ There exist no algorithms for deciding whether any given context-free grammar is ambiguous. Show that if the language $L(G_A)\space \cap L(G_B) $ in The...

Rishi yadav

162 views

Rishi yadav asked Mar 16, 2019

0 votes

0 answers

9196

Peter Linz Edition 5 Exercise 12.4 Question 3 (Page No. 321)
Show that for arbitrary context-free grammars $G_1$ and $G_2$, the problem $”L(G_1) \space\cap L(G_2) $ is context-free$”$ is undecidable.

Show that for arbitrary context-free grammars $G_1$ and $G_2$, the problem $”L(G_1) \space\cap L(G_2) $ is context-free$”$ is undecidable.

Rishi yadav

153 views

Rishi yadav asked Mar 16, 2019

0 votes

0 answers

9197

Peter Linz Edition 5 Exercise 12.4 Question 2 (Page No. 321)
Show that the problem of determining whether or not $L(G_1) \subseteq L(G_2)$ is undecidable for context-free grammars $G_1,\space G_2$.

Show that the problem of determining whether or not $L(G_1) \subseteq L(G_2)$ is undecidable for context-free grammars $G_1,\space G_2$.

Rishi yadav

138 views

Rishi yadav asked Mar 16, 2019

0 votes

0 answers

9198

Peter Linz Edition 5 Exercise 12.4 Question 1 (Page No. 320)
$\text{Theorem}:$ There exists no algorithm for deciding whether any given context-free grammar is ambiguous. Prove the claim made in Theorem that $G_A$ and $G_B$ by themselves are unambiguous

$\text{Theorem}:$ There exists no algorithm for deciding whether any given context-free grammar is ambiguous.Prove the claim made in Theorem that $G_A$ and $G_B$ by thems...

Rishi yadav

163 views

Rishi yadav asked Mar 16, 2019

0 votes

0 answers

9199

Peter Linz Edition 5 Exercise 12.3 Question 6 (Page No. 318)
The correspondence pair $(A, B)$ is said to have an even PC solution if and only if there exists a nonempty sequence of even integers $i,j,..k$ such that $w_iw_j...w_k = v_iv_j...v_k$. Show that the problem of deciding whether or not an arbitrary pair $(A, B)$ has an even PC solution is undecidable.

The correspondence pair $(A, B)$ is said to have an even PC solution if and only if there exists a nonempty sequence of even integers $i,j,..k$ such that $w_iw_j...w_k = ...

Rishi yadav

352 views

Rishi yadav asked Mar 16, 2019

0 votes

0 answers

9200

Peter Linz Edition 5 Exercise 12.3 Question 5 (Page No. 317,318)
Show that the following modifications of the Post correspondence problem are undecidable. $\text(a)$ There is an MPC solution if there is a sequence of integers such that $w_iw_j...w_kw_1 = v_iv_j...v_kv_i$. $\text(b)$ There is an MPC solution if there is a sequence of integers such that $w_1w_2w_iw_j...w_k = v_1v_2v_iv_j...v_k$.

Show that the following modifications of the Post correspondence problem are undecidable.$\text(a)$ There is an MPC solution if there is a sequence of integers such that ...

Rishi yadav

306 views

Rishi yadav asked Mar 16, 2019

0 votes

0 answers

9201

Peter Linz Edition 5 Exercise 12.3 Question 4 (Page No. 317)
Suppose we restrict the domain of the Post correspondence problem to include only alphabets with exactly two symbols. Is the resulting correspondence problem decidable$?$

Suppose we restrict the domain of the Post correspondence problem to include only alphabets with exactly two symbols. Is the resulting correspondence problem decidable$?$...

Rishi yadav

390 views

Rishi yadav asked Mar 16, 2019

0 votes

0 answers

9202

Peter Linz Edition 5 Exercise 12.3 Question 3 (Page No. 317)
Show that for $|\Sigma| = 1$, the Post correspondence problem is decidable, that is, there is an algorithm that can decide whether or not $(A, B)$ has a $\text{PC}$ solution for any given $(A, B)$ on a single-letter alphabet.

Show that for $|\Sigma| = 1$, the Post correspondence problem is decidable, that is, there is an algorithm that can decide whether or not $(A, B)$ has a $\text{PC}$ solut...

Rishi yadav

213 views

Rishi yadav asked Mar 16, 2019

0 votes

0 answers

9203

Peter Linz Edition 5 Exercise 12.3 Question 2 (Page No. 317)
$\text{Theorem}:$ Let $G = (V, T, S, P )$ be an unrestricted grammar, with w any string in $T^+$. Let $(A, B)$ be the correspondence pair constructed from $G$ and $w$ be the process exhibited in Figure. Then the ... string $F$ as $v_1$. The order of the rest of the strings is immaterial. Provide the details of the proof of the Theorem.

$\text{Theorem}:$ Let $G = (V, T, S, P )$ be an unrestricted grammar, with w any string in $T^+$. Let $(A, B)$ be the correspondence pair constructed from $G$ and $w$ be ...

Rishi yadav

158 views

Rishi yadav asked Mar 16, 2019

0 votes

0 answers

9204

Peter Linz Edition 5 Exercise 12.3 Question 1 (Page No. 317)
Let $A = \{001, 0011, 11, 101\}$ and $B = \{01, 111, 111, 010\}$. Does the pair $(A, B)$ have a PC solution$?$ Does it have an MPC solution$?$

Let $A = \{001, 0011, 11, 101\}$ and $B = \{01, 111, 111, 010\}$. Does the pair $(A, B)$ have a PC solution$?$ Does it have an MPC solution$?$

Rishi yadav

226 views

Rishi yadav asked Mar 16, 2019

0 votes

0 answers

9205

State Diagram of Sequential circuit

Na462

1.2k views

Na462 asked Mar 16, 2019

0 votes

0 answers

9206

Self thought
We know that Regular languages are decidable under membership property and lets say $L$ is such a regular language. From Chomsky hierarchy we know that $\text{Regular languages}$ $\subset$ $\text{Recursively Enumerable Languages}$. Lets say there are two persons $A$ ... how can we conclude that $M$ will halt after processing $L$ or will not halt at all. Please explain with reason?

We know that Regular languages are decidable under membership property and lets say $L$ is such a regular language. From Chomsky hierarchy we know that $\text{Regular lan...

!KARAN

622 views

!KARAN asked Mar 16, 2019

2 votes

0 answers

9207

Andrew S. Tanenbaum Edition 5th Exercise 5 Question 26 (Page No. 492)
Suppose that instead of using 16 bits for the network part of a class B address originally, 20 bits had been used. How many class B networks would there have been?

Suppose that instead of using 16 bits for the network part of a class B address originally,20 bits had been used. How many class B networks would there have been?

ajaysoni1924

1.4k views

ajaysoni1924 asked Mar 16, 2019

0 votes

1 answer

9208

Andrew S. Tanenbaum Edition 5th Exercise 5 Question 24 (Page No. 492)
A router is blasting out IP packets whose total length (data plus header) is 1024 bytes. Assuming that packets live for 10 sec, what is the maximum line speed the router can operate at without danger of cycling through the IP datagram ID number space?

A router is blasting out IP packets whose total length (data plus header) is 1024 bytes.Assuming that packets live for 10 sec, what is the maximum line speed the router c...

ajaysoni1924

350 views

ajaysoni1924 asked Mar 16, 2019

0 votes

0 answers

9209

Andrew S. Tanenbaum Edition 5th Exercise 5 Question 23 (Page No. 492)
Suppose that host A is connected to a router R 1, R 1 is connected to another router, R 2, and R 2 is connected to host B. Suppose that a TCP message that contains 900 bytes of data and 20 bytes of TCP header is ... 8-byte frame header, and link R2-B can support a maximum frame size of 512 bytes including a 12-byte frame header

Suppose that host A is connected to a router R 1, R 1 is connected to another router,R 2, and R 2 is connected to host B. Suppose that a TCP message that contains 900byte...

ajaysoni1924

383 views

ajaysoni1924 asked Mar 16, 2019

0 votes

1 answer

9210

Andrew S. Tanenbaum Edition 5th Exercise 5 Question 18 (Page No. 491)
A token bucket scheme is used for traffic shaping. A new token is put into the bucket every 5 μsec. Each token is good for one short packet, which contains 48 bytes of data. What is the maximum sustainable data rate?

A token bucket scheme is used for traffic shaping. A new token is put into the bucketevery 5 μsec. Each token is good for one short packet, which contains 48 bytes ofdat...

ajaysoni1924

6.5k views

ajaysoni1924 asked Mar 16, 2019

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