Recent questions without answers / GATE Overflow for GATE CSE

Give a construction by which an arbitrary context-free grammar can be used in the proof of Theorem 7.1.Theorem 7.1: For any context-free language L, there exists an npda ...

Naveen Kumar 3

393 views

Naveen Kumar 3 asked Jun 23, 2019

0 votes

0 answers

4087

Peter Linz Edition 4 Exercise 7.2 Question 17 (Page No. 196)
Give full details of the proof of Theorem 7.2 . Theorem 7.2 : If L = L (M) for some npda M, then L is a context-free language.

Give full details of the proof of Theorem 7.2 .Theorem 7.2 : If L = L (M) for some npda M, then L is a context-free language.

Naveen Kumar 3

299 views

Naveen Kumar 3 asked Jun 23, 2019

0 votes

0 answers

4088

Peter Linz Edition 4 Exercise 7.2 Question 15 (Page No. 195)
Find a context-free grammar that generates the language accepted by the npda $M =$ ({$q_0,q_1$}, {$a,b$}, {$A, z$}$,δ, q_0, z,$ {$q_1$}), with transitions $δ(q_0, a,z) =$ {$(q_0, Az)$}, $δ (q_0,b, A) =$ {$(q_0, AA)$}, $δ(q_0, a, A) =$ {$(q_1,λ)$}.

Find a context-free grammar that generates the language accepted by the npda $M =$ ({$q_0,q_1$}, {$a,b$}, {$A, z$}$,δ, q_0, z,$ {$q_1$}), with transitions ...

Naveen Kumar 3

314 views

Naveen Kumar 3 asked Jun 23, 2019

0 votes

0 answers

4089

Peter Linz Edition 4 Exercise 7.2 Question 14 (Page No. 195)
find an npda for the language $L = ${ $ww^R : w ∈$ {a, b}$^+ $}

find an npda for the language $L = ${ $ww^R : w ∈$ {a, b}$^+ $}

Naveen Kumar 3

287 views

Naveen Kumar 3 asked Jun 23, 2019

0 votes

0 answers

4090

Peter Linz Edition 4 Exercise 7.2 Question 11,12,13 (Page No. 195)
Show that the npda in Example 7.8 accepts L (aa*b). Find the grammar that generates Example 7.8 and prove that this grammar generates the language L (aa*b). show that the variable ($q_0zq_1$) is useless. (see page no. 191-193) Example 7.8 : ... $\delta(q_0,b,A)=${$(q_1,\lambda)$}, $\delta(q_1,\lambda,z)=${$(q_2,\lambda)$}.

Show that the npda in Example 7.8 accepts L (aa*b).Find the grammar that generates Example 7.8 and prove that this grammar generates the language L (aa*b).show that the v...

Naveen Kumar 3

400 views

Naveen Kumar 3 asked Jun 23, 2019

0 votes

0 answers

4091

Peter Linz Edition 4 Exercise 7.2 Question 7,8 (Page No. 195)
Show that “For every npda $M$, there exists an npda $\widehat M$ with at most three states, such that $L (M) = L (\widehat M )$. Show how the number of states of $\widehat M $ in the above exercise can be reduced to two.

Show that “For every npda $M$, there exists an npda $\widehat M$ with at most three states, such that $L (M) = L (\widehat M )$.Show how the number of states of $\wideh...

Naveen Kumar 3

214 views

Naveen Kumar 3 asked Jun 22, 2019

0 votes

0 answers

4092

Peter Linz Edition 4 Exercise 7.2 Question 5 (Page No. 195)
Construct an npda corresponding to the grammar $S\rightarrow aABB|aAA,$ $A\rightarrow aBB|a,$ $B\rightarrow bBB|A.$

Construct an npda corresponding to the grammar $S\rightarrow aABB|aAA,$ $A\rightarrow aBB|a,$ $B\rightarrow bBB|A.$

Naveen Kumar 3

266 views

Naveen Kumar 3 asked Jun 22, 2019

0 votes

0 answers

4093

Peter Linz Edition 4 Exercise 7.2 Question 3 (Page No. 195)
Construct an npda that accepts the language generated by the grammar $S\rightarrow aSbb|aab$.

Construct an npda that accepts the language generated by the grammar $S\rightarrow aSbb|aab$.

Naveen Kumar 3

201 views

Naveen Kumar 3 asked Jun 22, 2019

0 votes

0 answers

4094

Peter Linz Edition 4 Exercise 7.2 Question 2 (Page No. 195)
Prove that the pda in Example 7.6 accepts the language $L =$ {$a^{n+1}b^{2n} : n ≥ 0$ }.

Prove that the pda in Example 7.6 accepts the language $L =$ {$a^{n+1}b^{2n} : n ≥ 0$ }.

Naveen Kumar 3

189 views

Naveen Kumar 3 asked Jun 22, 2019

0 votes

0 answers

4095

Peter Linz Edition 4 Exercise 7.2 Question 1 (Page No. 195)
Show that the pda constructed in Example 7.6 accepts the string $aaabbbb$ that is in the language generated by the given grammar. Example 7.6: Construct a pda that accepts the language generated by a grammar with productions $S\rightarrow aSbb|a.$

Show that the pda constructed in Example 7.6 accepts the string $aaabbbb$ that is in the languagegenerated by the given grammar.Example 7.6: Construct a pda that accepts...

Naveen Kumar 3

195 views

Naveen Kumar 3 asked Jun 22, 2019

0 votes

0 answers

4096

Peter Linz Edition 4 Exercise 7.1 Question 16 (Page No. 184)
We can define a restricted npda as one that can increase the length of the stack by at most one symbol in each move, changing Definition 7.1 so that $\delta :$Q x $(\sum \cup$ {$\lambda$}$) $ ... the initial state of the control unit, $z ∈ Γ$ is the stack start symbol, $F ⊆ Q$ is the set of final states.

We can define a restricted npda as one that can increase the length of the stack by at most onesymbol in each move, changing Definition 7.1 so that $\...

Naveen Kumar 3

714 views

Naveen Kumar 3 asked Jun 22, 2019

0 votes

0 answers

4097

Peter Linz Edition 4 Exercise 7.1 Question 14 (Page No. 184)
Find an npda with no more than two internal states that accepts the language $L (aa^*ba^*)$.

Find an npda with no more than two internal states that accepts the language $L (aa^*ba^*)$.

Naveen Kumar 3

250 views

Naveen Kumar 3 asked Jun 22, 2019

0 votes

0 answers

4098

Peter Linz Edition 4 Exercise 7.1 Question 13 (Page No. 184)
What language is accepted by the npda in Exercise 11 if we use $F =$ {$q_0, q_1, q_2$}?

What language is accepted by the npda in Exercise 11 if we use $F =$ {$q_0, q_1, q_2$}?

Naveen Kumar 3

199 views

Naveen Kumar 3 asked Jun 22, 2019

0 votes

0 answers

4099

Peter Linz Edition 4 Exercise 7.1 Question 11 (Page No. 184)
What language is accepted by the npda $M =$ ({$q_0, q_1, q_2$}, {$a, b$}, {$a, b, z$}, $δ, q_0, z$, {$q_2$}) with transitions $\delta(q_0,a,z)=${$(q_1,a),(q_2,\lambda)$}, $\delta(q_1,b,a)=${$(q_1,b)$}, $\delta(q_1,b,b)=${$(q_1,b)$}, $\delta(q_1,a,b)=${$(q_2,\lambda)$} ?

What language is accepted by the npda $M =$ ({$q_0, q_1, q_2$}, {$a, b$}, {$a, b, z$}, $δ, q_0, z$, {$q_2$}) withtransitions $\delta(q_0,a,z)=${$(q_...

Naveen Kumar 3

246 views

Naveen Kumar 3 asked Jun 22, 2019

0 votes

0 answers

4100

Peter Linz Edition 4 Exercise 7.1 Question 10 (Page No. 184)
What language is accepted by the pda $M= (${$q_0,q_1,q_2,q_3,q_4,q_5$},{$a,b$},{$0,1,a$},$\delta,q_0,z,${$q_5$}), with $\delta(q_0,b,z)=${$(q_1,1z)$}, $\delta(q_0,b,1)=${$(q_1,11)$}, $\delta(q_2,a,1)=${$(q_3,\lambda)$}, $\delta(q_3,a,1)=${$(q_4,\lambda)$} $\delta(q_4,a,z)=${$(q_4,z),(q_5,z)$} ?

What language is accepted by the pda $M= (${$q_0,q_1,q_2,q_3,q_4,q_5$},{$a,b$},{$0,1,a$},$\delta,q_0,z,${$q_5$}),with $\delta(q_0,b,z)=...

Naveen Kumar 3

216 views

Naveen Kumar 3 asked Jun 22, 2019

0 votes

0 answers

4101

Proving a problem as NP-complete.
According to this article, A problem X can be proved to be NP-complete if an already existing NP-complete problem (say Y) can be polynomial-time reduced to current problem X. The problem also needs to be NP. Now my question is: Do we also ... have to be only one way to prove a problem is NP-complete? PS: I have already asked this question in cs.stackexchange

According to this article, A problem X can be proved to be NP-complete if an already existing NP-complete problem (say Y) can be polynomial-time reduced to current proble...

commenter commenter

866 views

commenter commenter asked Jun 14, 2019

0 votes

0 answers

4102

Is each and every NP complete problem (polynomially) reduced to each and every another NP complete problem?

I know that all NP problems can be reduced to Boolean Satisfiability SAT problem. But my question is whether SAT problem can be reduced to other NP complete problems like...

commenter commenter

358 views

commenter commenter asked Jun 13, 2019

0 votes

0 answers

4103

How do a^n! and a^n^2 come under machine Linear Bound Automata?I know that LBA is a reduced form of standard Turing Machine where tape is restricted to be used for inputs...

Akash Kumar Roy

622 views

Akash Kumar Roy asked Jun 12, 2019

0 votes

0 answers

4104

Discrete mathematics 7th ed by Kenneth Rosen,chapter3:Algorithm
Should not there be a second condition stating i = j-1 in While loop's conditional statement,if not then it seems to me while loop will be a infinite loop..

Should not there be a second condition stating i = j-1 in While loop's conditional statement,if not then it seems to me while loop will be a infinite loop..

souren

1.0k views

souren asked Jun 12, 2019

0 votes

0 answers

4105

Admission in iiitm kerala
Hello I have not performed well in the gate this year, I am not getting any IIT. Although I applied in IIITMK, Kerala does anyone know how good it is to do masters there.? because it is not possible for me to took gap this year. please help thanks in advance

Hello I have not performed well in the gate this year, I am not getting any IIT. Although I applied in IIITMK, Kerala does anyone know how good it is to do masters there....

JPranavc

466 views

JPranavc asked Jun 11, 2019

–1 votes

0 answers

4106

Self Doubt-Little/big endian-GeeksforGeeks
#include <stdio.h> int main() { unsigned char arr[2] = {0x01, 0x00}; unsigned short int x = *(unsigned short int *) arr; printf("%d", x); getchar(); return 0; } Output in little endian and big endian ? Please someone provide a detailed explanation if possible with diagram.

#include <stdio.h>int main(){ unsigned char arr = {0x01, 0x00}; unsigned short int x = *(unsigned short int *) arr; printf("%d", x); getchar(); return 0;}...

KUSHAGRA गुप्ता

415 views

KUSHAGRA गुप्ता asked Jun 9, 2019

0 votes

0 answers

4107

Cd me test

Deepalitrapti

353 views

Deepalitrapti asked Jun 7, 2019

0 votes

0 answers

4108

When will u start the go classroom classes?

Moni Alex

423 views

Moni Alex asked Jun 6, 2019

1 votes

0 answers

4109

Precision Field in printf with %s specifier
We know that UNIX support a feature that allows for variable field with precision. please help me out in this statement -> printf(“% * .* s \n”,w,d,string); ? i know using of precision with string such as %10.4s <width>.<precision> indicating that first four character to be printed in a field with 10 columns.

We know that UNIX support a feature that allows for variable field with precision.please help me out in this statement ->printf(“% * .* s \n”,w,d,string); ?i know us...

Aks9639

366 views

Aks9639 asked Jun 6, 2019

0 votes

0 answers

4110

Compiler Design: Self Doubt on Operator Grammar
Say I have a grammar, S→ AB A→ a B→ b This grammar is not operator grammar as 2 non terminals are lying side by side, but can be converted to an operator grammar. S→ ab , A→ a , B→ b here i have a doubt, operator grammar ... can we operate even two terminal symbols when placed side by side? Isn't it same as placing 2 non-terminal symbol side by side?

Say I have a grammar, S→ AB A→ a B→ bThis grammar is not operator grammar as 2 non ter...

Hirak

615 views

Hirak asked Jun 6, 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