Recent questions tagged peter-linz / GATE Overflow for GATE CSE

1 votes

0 answers

271

Peter Linz Edition 4 Exercise 3.3 Question 17 (Page No. 97)
Let $G_1 = (V_1,Σ,S_1,P_1)$ be right-linear and $G_2= (V_2, Σ,S_2,P_2)$ be a left-linear grammar, and assume that $V_1$ and $V_2$ are disjoint. Consider the linear grammar $G =(${$S$}$ ∪ V_1 ∪ V_2, Σ,S, P)$, where $S$ is not in $V_1 ∪ V_2$ and $P =$ {$S → S_1|S_2$}$ ∪ P_1 ∪ P_2$. Show that $L(G)$ is regular.

Let $G_1 = (V_1,Σ,S_1,P_1)$ be right-linear and $G_2= (V_2, Σ,S_2,P_2)$ be a left-linear grammar, and assume that $V_1$ and $V_2$ are disjoint. Consider the linear gram...

Naveen Kumar 3

194 views

Naveen Kumar 3 asked Apr 3, 2019

0 votes

2 answers

272

Peter Linz Edition 4 Exercise 3.3 Question 15 (Page No. 97)
Show that any regular grammar $G$ for which $L (G) ≠ Ø$ must have at least one production of the form $A → x$ where $A ∈ V$ and $x ∈ T^ *$.

Show that any regular grammar $G$ for which $L (G) ≠ Ø$ must have at least one production of the form $A → x$ where $A ∈ V$ and $x ∈ T^ *$.

Naveen Kumar 3

361 views

Naveen Kumar 3 asked Apr 3, 2019

0 votes

0 answers

273

Peter Linz Edition 4 Exercise 3.3 Question 14 (Page No. 97)
Show that for every regular language not containing $λ$ there exists a right-linear grammar whose productions are restricted to the forms $A → aB$, or $A → a$, where $A, B ∈ V,$ and $a ∈ T$

Show that for every regular language not containing $λ$ there exists a right-linear grammar whose productions are restricted to the forms ...

Naveen Kumar 3

241 views

Naveen Kumar 3 asked Apr 3, 2019

0 votes

0 answers

274

Peter Linz Edition 4 Exercise 3.3 Question 13 (Page No. 97)
Find regular grammars for the following languages on {$ a, b$}. (a) $L=${$w:n_a(w)$ and $n_b(w)$ are both even}. (b) $L=${$w:(n_a(w)$ - $n_b(w))$ mod $3=1$}. (c) $L=${$w:(n_a(w)$ - $n_b(w))$ mod $3\neq1$}. (d) $L=${$w:(n_a(w)$ - $n_b(w))$ mod $3\neq0$}. (e) $L=${$w:|n_a(w)$ - $n_b(w)|$ is odd}.

Find regular grammars for the following languages on {$ a, b$}. (a) $L=${$w:n_a(w)$ and $n_b(w)$ are both even}. (b) $L=${$w:(n_a(w)$ - $n_b(w))$ mod $3=1$}. (c) $L=${$w:...

Naveen Kumar 3

226 views

Naveen Kumar 3 asked Apr 3, 2019

0 votes

0 answers

275

Peter Linz Edition 4 Exercise 3.3 Question 12 (Page No. 97)
Find a regular grammar that generates the language $L=$ {$w∈$ {$a,b$}$^*:n_a(w)+3n_b(w)$ is even } .

Find a regular grammar that generates the language $L=$ {$w∈$ {$a,b$}$^*:n_a(w)+3n_b(w)$ is even } .

Naveen Kumar 3

165 views

Naveen Kumar 3 asked Apr 3, 2019

0 votes

0 answers

276

Peter Linz Edition 4 Exercise 3.3 Question 11 (Page No. 97)
Find a regular grammar for the language $L =$ {$a^nb^m : n + m$ is even}.

Find a regular grammar for the language $L =$ {$a^nb^m : n + m$ is even}.

Naveen Kumar 3

173 views

Naveen Kumar 3 asked Apr 3, 2019

0 votes

0 answers

277

Peter Linz Edition 4 Exercise 3.3 Question 10 (Page No. 97)
Find a left-linear grammar for the language $L ((aab^*ab)^*).$

Find a left-linear grammar for the language $L ((aab^*ab)^*).$

Naveen Kumar 3

153 views

Naveen Kumar 3 asked Apr 3, 2019

0 votes

0 answers

278

Peter Linz Edition 4 Exercise 3.3 Question 7 (Page No. 97)
Find a regular grammar that generates the language on $Σ =$ {$a, b$} consisting of all strings with no more than three $a$'s.

Find a regular grammar that generates the language on $Σ =$ {$a, b$} consisting of all strings with nomore than three $a$'s.

Naveen Kumar 3

163 views

Naveen Kumar 3 asked Apr 3, 2019

0 votes

1 answer

279

Peter Linz Edition 4 Exercise 3.3 Question 5 (Page No. 96)
Find a left-linear grammar for the language accepted by the nfa below.

Find a left-linear grammar for the language accepted bythe nfa below.

Naveen Kumar 3

496 views

Naveen Kumar 3 asked Apr 3, 2019

0 votes

0 answers

280

Peter Linz Edition 4 Exercise 3.3 Question 4 (Page No. 96)
Construct right- and left-linear grammars for the language $L =$ {$a^nb^m : n ≥ 2, m ≥ 3$}.

Construct right- and left-linear grammars for the language$L =$ {$a^nb^m : n ≥ 2, m ≥ 3$}.

Naveen Kumar 3

202 views

Naveen Kumar 3 asked Apr 3, 2019

0 votes

0 answers

281

Peter Linz Edition 4 Exercise 3.3 Question 3 (Page No. 96)
Construct a left-linear grammar for the language generated by the grammar $S → abA,$ $A → baB,$ $B → aA|bb.$

Construct a left-linear grammar for the language generated by the grammar$S → abA,$$A → baB,$$B → aA|bb.$

Naveen Kumar 3

198 views

Naveen Kumar 3 asked Apr 3, 2019

0 votes

0 answers

282

Peter Linz Edition 4 Exercise 3.3 Question 2 (Page No. 96)
Find a regular grammar that generates the language $L (aa^* (ab+ a)^*)$ .

Find a regular grammar that generates the language $L (aa^* (ab+ a)^*)$ .

Naveen Kumar 3

201 views

Naveen Kumar 3 asked Apr 3, 2019

0 votes

0 answers

283

Peter Linz Edition 4 Exercise 3.3 Question 1 (Page No. 96)
Construct a dfa that accepts the language generated by the grammar $S → abA, A → baB, B → aA|bb$ .

Construct a dfa that accepts the language generated by the grammar$S → abA,A → baB,B → aA|bb$ .

Naveen Kumar 3

220 views

Naveen Kumar 3 asked Apr 3, 2019

0 votes

0 answers

284

Peter Linz Edition 4 Exercise 3.2 Question 18 (Page No. 89)
Find nfa's for $L (aØ)$ and $L (Ø^*)$. Is the result consistent with the definition of these languages?

Find nfa's for $L (aØ)$ and $L (Ø^*)$. Is the result consistent with the definition of these languages?

Naveen Kumar 3

187 views

Naveen Kumar 3 asked Apr 3, 2019

1 votes

0 answers

285

Peter Linz Edition 4 Exercise 3.2 Question 17 (Page No. 89)
Analogous to the previous exercise, consider all words that can be formed from $L$ by dropping a single symbol of the string. Formally define this operation drop for languages. Construct an nfa for $drop (L)$, given an nfa for $L$.

Analogous to the previous exercise, consider all words that can be formed from $L$ by droppinga single symbol of the string. Formally define this operation drop for langu...

Naveen Kumar 3

299 views

Naveen Kumar 3 asked Apr 3, 2019

0 votes

0 answers

286

Peter Linz Edition 4 Exercise 3.2 Question 16 (Page No. 89)
In some applications, such as programs that check spelling, we may not need an exact match of the pattern, only an approximate one. Once the notion of an approximate match has been made precise, automata theory can be applied to ... this to write a pattern-recognition program for $insert (L)$, using as input a regular expression for $L$.

In some applications, such as programs that check spelling, we may not need an exact match ofthe pattern, only an approximate one. Once the notion of an approximate match...

Naveen Kumar 3

329 views

Naveen Kumar 3 asked Apr 3, 2019

0 votes

0 answers

287

Peter Linz Edition 4 Exercise 3.2 Question 15 (Page No. 89)
Write a regular expression for the set of all $C$ real numbers.

Write a regular expression for the set of all $C$ real numbers.

Naveen Kumar 3

177 views

Naveen Kumar 3 asked Apr 3, 2019

0 votes

2 answers

288

Peter Linz Edition 4 Exercise 3.2 Question 13 (Page No. 88)
Find a regular expression for the following languages on {$a, b$}. (a) $L =$ {$w : n_a (w)$ and $n_b (w)$ are both even}. (b) $L =$ {$w :(n_a (w) - n_b (w))$ mod $3 = 1$}. (c) $L =$ {$w :(n_a (w) - n_b (w))$ mod $3 = 0$}. (d) $L =$ {$w :2n_a (w)+3n_b (w)$ is even}.

Find a regular expression for the following languages on {$a, b$}.(a) $L =$ {$w : n_a (w)$ and $n_b (w)$ are both even}.(b) $L =$ {$w :(n_a (w) - n_b (w))$ mod $3 = 1$}.(...

Naveen Kumar 3

551 views

Naveen Kumar 3 asked Apr 3, 2019

0 votes

0 answers

289

Peter Linz Edition 5 Exercise 9.1 Question 7(b) (Page No. 238)
Construct Turing machines that will accept the following languages on $\{a,b\}$ $L = \{w:|w| \text{ is even }\}$.

Construct Turing machines that will accept the following languages on $\{a,b\}$ $L = \{w:|w| \te...

Rishi yadav

277 views

Rishi yadav asked Apr 3, 2019

0 votes

0 answers

290

Peter Linz Edition 5 Exercise 9.1 Question 7(a) (Page No. 238)
Construct Turing machines that will accept the following languages on $\{a,b\}$. $L = L(aba^*b)$.

Construct Turing machines that will accept the following languages on $\{a,b\}$. $L = L(ab...

Rishi yadav

247 views

Rishi yadav asked Apr 3, 2019

0 votes

0 answers

291

Peter Linz Edition 5 Exercise 9.1 Question 6 (Page No. 238)
$\text{Example}:$ Design a Turing machine that copies strings of $1’s$. More precisely, find a machine that performs the computation $q_0q\vdash^*q_fww,$ for any $w\in\{1\}^+$. What happens in Example if the string $w$ contains any symbol other than $1?$

$\text{Example}:$ Design a Turing machine that copies strings of $1’s$. More precisely, find a machine that performs the computation ...

Rishi yadav

151 views

Rishi yadav asked Apr 3, 2019

0 votes

1 answer

292

Peter Linz Edition 5 Exercise 9.1 Question 5 (Page No. 238)
What language is accepted by the Turing machine whose transition graph is in the figure below$?$

What language is accepted by the Turing machine whose transition graph is in the figure below$?$

Rishi yadav

1.0k views

Rishi yadav asked Apr 3, 2019

0 votes

0 answers

293

Peter Linz Edition 5 Exercise 9.1 Question 4 (Page No. 238)
$\text{Example}:$ For $\Sigma = \{a,b\}$ design a Turing machine that accepts $L = \{a^nb^n:n\geq 1\}$. Is there any input for which the Turing machine in Example goes into an infinite loop$?$

$\text{Example}:$ For $\Sigma = \{a,b\}$ design a Turing machine that accepts $L = \{a^nb^n:...

Rishi yadav

126 views

Rishi yadav asked Apr 3, 2019

0 votes

1 answer

294

Peter Linz Edition 5 Exercise 9.1 Question 3 (Page No. 238)
$\text{Example}:$ For $\Sigma = \{a,b\}$ design a Turing machine that accepts $L = \{a^nb^n:n\geq 1\}$. Determine what the Turing machine in Example does when presented with the inputs $aba$ and $aaabbbb$.

$\text{Example}:$ For $\Sigma = \{a,b\}$ design a Turing machine that accepts $L = \{a^nb^n:...

Rishi yadav

205 views

Rishi yadav asked Apr 3, 2019

0 votes

0 answers

295

Peter Linz Edition 5 Exercise 9.1 Question 2 (Page No. 238)
Design a Turing machine with no more than three states that accept the language $L(a(a+b)^*)$. Assume that $\Sigma = \{a,b\}$. Is it possible to do this with a two-state machine$?$

Design a Turing machine with no more than three states that accept the language $L(a(a+b)^*)$. Assume that $\Sigma = \{a,b\}$. Is it possible to do this with a two-state ...

Rishi yadav

166 views

Rishi yadav asked Apr 3, 2019

0 votes

0 answers

296

Peter Linz Edition 5 Exercise 9.1 Question 1 (Page No. 238)
Write a Turing machine simulator in some higher-level programming language. Such a simulator should accept as input the description of any Turing machine, together with an initial configuration, and should produce as output the result of the computation.

Write a Turing machine simulator in some higher-level programming language. Such a simulator should accept as input the description of any Turing machine, together with a...

Rishi yadav

270 views

Rishi yadav asked Apr 3, 2019

0 votes

0 answers

297

Peter Linz Edition 5 Exercise 10.5 Question 6,7 (Page No. 276)
$\text{Exercise}:6$ ... above exercise to show that any context-free language not containing $\lambda$ is accepted by some linear bounded automaton.

$\text{Exercise}:6$ Show that for every context-free language there exists an accepting pda, such that the number of symbols in the stack never exceeds the length of the...

Rishi yadav

201 views

Rishi yadav asked Apr 3, 2019

0 votes

0 answers

298

Peter Linz Edition 5 Exercise 10.5 Question 5 (Page No. 276)
$\text{Example}:$ Find a linear bounded automaton that accepts the language $L = \{a^{n!}:n\geq0\}$. Find a lba for the complement of the language in Example, assuming that $\Sigma = \{a,b\}$.

$\text{Example}:$ Find a linear bounded automaton that accepts the language $L = \{a^{n!}...

Rishi yadav

136 views

Rishi yadav asked Apr 3, 2019

0 votes

0 answers

299

Peter Linz Edition 5 Exercise 10.5 Question 4(f) (Page No. 276)
Find linear bounded automata for the following languages. $L =\Big \{www^R:w\in \{a,b\}^+\Big\}$.

Find linear bounded automata for the following languages. $L =\Big \{www^R:w\in \{a,b\}^+\Big\}$.

Rishi yadav

178 views

Rishi yadav asked Apr 3, 2019

0 votes

0 answers

300

Peter Linz Edition 5 Exercise 10.5 Question 4(e) (Page No. 276)
Find linear bounded automata for the following languages. $L = \Big\{w^n : w\in\{a,b\}^+,n\geq2\Big\}$.

Find linear bounded automata for the following languages. $L = \Big\{w^n : w\in\{a,b\}^+,n\geq2\Big\}$.

Rishi yadav

125 views

Rishi yadav asked Apr 3, 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