Search results for peter-linz+theory-of-computation / GATE Overflow for GATE CSE

0 votes

0 answers

1

Peter Linz Edition 5 Exercise 10.5 Question 3
Consider an offline Turing machine in which the input can be read only once, moving left to right, and not rewritten. On its work tape, it can use at most n extra cells for work space, where n is fixed for all inputs. Show that such a machine is equivalent to a finite automaton.

Consider an offline Turing machine in which the input can be read only once, moving left to right, and not rewritten. On its work tape, it can use at most n extra cells f...

borhanElmi

320 views

borhanElmi asked Feb 8, 2023

0 votes

0 answers

2

An Introduction to Formal Languages and Automata,Peter Linz,6th edition,exercise 3.3 q3
Find a regular grammar that generates the language L (aa ∗ (ab + a) ∗ ).

Find a regular grammar that generates the language L (aa ∗ (ab + a) ∗ ).

Silver_Reaper

522 views

Silver_Reaper asked Feb 6, 2023

0 votes

1 answer

3

An Introduction to Formal Languages and Automata,6th edition,Exercise 2.3 Q2.
Convert the nfa in Exercise 13, Section 2.2, into an equivalent dfa.

Convert the nfa in Exercise 13, Section 2.2, into an equivalent dfa.

Silver_Reaper

695 views

Silver_Reaper asked Jan 28, 2023

0 votes

0 answers

4

An Introduction to Formal Languages and Automata Peter Linz 6th Edition.Exercise 2.1 4 d,e
For Σ = {a, b}, construct dfa’s that accept the sets consisting of: (d) all strings with at least one b and exactly two a’s. (e) all the strings with exactly two a’s and more than three b’s.

For Σ = {a, b}, construct dfa’s that accept the sets consisting of:(d) all strings with at least one b and exactly two a’s.(e) all the strings with exactly two a’s...

Silver_Reaper

397 views

Silver_Reaper asked Jan 24, 2023

0 votes

1 answer

5

Peter Linz Edition 4 Exercise 6.2 Question 14 (Page No. 170)
Can every linear grammar be converted to a form in which all productions look like $A → ax,$ where $a∈ T$ and $x∈V$ $\cup$ {$\lambda$} ?

Can every linear grammar be converted to a form in which all productions look like $A → ax,$ where $a∈ T$ and $x∈V$ $\cup$ {$\lambda$} ?

Naveen Kumar 3

387 views

Naveen Kumar 3 asked Apr 19, 2019

0 votes

1 answer

6

Peter Linz Edition 4 Exercise 2.1 Question 16 (Page No. 48)
Show that the set of all real numbers in $C$ is a regular language.

Show that the set of all real numbers in $C$ is a regular language.

Naveen Kumar 3

955 views

Naveen Kumar 3 asked Mar 20, 2019

1 votes

1 answer

7

Peter Linz Edition 4 Exercise 4.3 Question 1 (Page No. 122)
Prove the following version of the pumping lemma. If $L$ is regular, then there is an $m$ such that, every $w ∈ L$ of length greater than $m$ can be decomposed as $w = xyz,$ with $|yz| ≤ m$ and $|y| ≥ 1,$ such that $xy^iz$ is in $L$ for all $i$.

Prove the following version of the pumping lemma. If $L$ is regular, then there is an $m$ such that,every $w ∈ L$ of length greater than $m$ can be decomposed as $w = x...

Naveen Kumar 3

263 views

Naveen Kumar 3 asked Apr 11, 2019

2 votes

2 answers

8

Peter Linz Edition 4 Exercise 1.2 Question 4 (Page No. 28)
Let $L$={$ab,aa,baa$}. Which of the following strings are in $L^*$ : $abaabaaabaa$, $aaaabaaaa$, $baaaaabaaaab$, $baaaaabaa$? Which strings are in $L^4$?

Let $L$={$ab,aa,baa$}.Which of the following strings are in $L^*$ :$abaabaaabaa$, $aaaabaaaa$, $baaaaabaaaab$, $baaaaabaa$? Which strings are in $L^4$?

Naveen Kumar 3

377 views

Naveen Kumar 3 asked Mar 17, 2019

7 votes

2 answers

9

Peter Linz Edition 4 Exercise 2.1 Question 2.d, 2.e (Page No. 47)
(d) all strings with at least one a and exactly two b’s (e) all the strings with exactly two a’s and more than two b’s.

(d) all strings with at least one a and exactly two b’s(e) all the strings with exactly two a’s and more than two b’s.

Pravin Paikrao

18.8k views

Pravin Paikrao asked Nov 2, 2016

4 votes

6 answers

10

Peter Linz Edition 4 Exercise 2.1 Question 6 (Page No. 47)
With $Σ = \{a,b\},$ give a DFA for $L = \{w_1aw_2: |w_1|\geq 3, |w_2|\leq 5\}.$

With $Σ = \{a,b\},$ give a DFA for $L = \{w_1aw_2: |w_1|\geq 3, |w_2|\leq 5\}.$

Naveen Kumar 3

10.0k views

Naveen Kumar 3 asked Mar 19, 2019

2 votes

1 answer

11

Peter Linz Exercise 3.2 Question 2
Find a NFA that accepts the complement of the language (ab*aa + bba*ab)

Find a NFA that accepts the complement of the language (ab*aa + bba*ab)

ankit-saha

1.2k views

ankit-saha asked Mar 26, 2022

0 votes

1 answer

12

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

206 views

Rishi yadav asked Apr 3, 2019

1 votes

1 answer

13

Peter Linz Edition 4 Exercise 3.1 Question 17 (Page No. 76)
Write regular expressions for the following languages on {$0, 1$}. (a) all strings ending in $01$, (b) all strings not ending in $01$, (c) all strings containing an even number of $0$'s, (d) Peter Linz Edition 4 ... (e) all strings with at most two occurrences of the substring $00$, (f) all strings not containing the substring $101$.

Write regular expressions for the following languages on {$0, 1$}.(a) all strings ending in $01$,(b) all strings not ending in $01$,(c) all strings containing an even num...

Naveen Kumar 3

844 views

Naveen Kumar 3 asked Mar 31, 2019

2 votes

2 answers

14

Peter Linz Edition 4 Exercise 8.1 Question 5 (Page No. 212)
Is the language L = {$a^nb^m : n = 2^m$} context-free?

Is the language L = {$a^nb^m : n = 2^m$} context-free?

Naveen Kumar 3

605 views

Naveen Kumar 3 asked Jun 25, 2019

1 votes

2 answers

15

Peter Linz Edition 4 Exercise 3.1 Question 12 (Page No. 76)
Find a regular expression for the complement of the language in $L (r) =$ {$a^{2n}b^{2m+1}: n ≥ 0, m ≥ 0$}.

Find a regular expression for the complement of the language in $L (r) =$ {$a^{2n}b^{2m+1}: n ≥ 0, m ≥ 0$}.

Naveen Kumar 3

489 views

Naveen Kumar 3 asked Mar 31, 2019

1 votes

2 answers

16

Peter Linz Edition 4 Exercise 3.1 Question 1 (Page No. 75)
Find all strings in $L((a + b) b (a + ab)^*)$ of length less than four.

Find all strings in $L((a + b) b (a + ab)^*)$ of length less than four.

Naveen Kumar 3

708 views

Naveen Kumar 3 asked Mar 31, 2019

1 votes

1 answer

17

Peter Linz Edition 4 Exercise 3.1 Question 15 (Page No. 76)
Find a regular expression for $L =$ {$w∈ $ {$0,1$}$^* : w$ has exactly one pair of consecutive zeros} .

Find a regular expression for$L =$ {$w∈ $ {$0,1$}$^* : w$ has exactly one pair of consecutive zeros} .

Naveen Kumar 3

565 views

Naveen Kumar 3 asked Mar 31, 2019

0 votes

0 answers

18

Peter Linz Edition 5 Exercise 2.2 Question 7 (Page No. 79)
Design an nfa with no more than five states for the set $\left \{ abab^n: n >0 \right \} \cup \left \{ ab{a}^n : n\geq 0 \right \}$

Design an nfa with no more than five states for the set $\left \{ abab^n: n >0 \right \} \cup \left \{ ab{a}^n : n\geq 0 \right \}$

ankit-saha

406 views

ankit-saha asked Mar 19, 2022

1 votes

1 answer

19

Peter Linz Edition 4 Exercise 3.1 Question 11 (Page No. 76)
Find a regular expression for $L =$ {$ab^nw: n ≥ 3, w ∈$ {$a, b$}$^+$}.

Find a regular expression for $L =$ {$ab^nw: n ≥ 3, w ∈$ {$a, b$}$^+$}.

Naveen Kumar 3

241 views

Naveen Kumar 3 asked Mar 31, 2019

1 votes

1 answer

20

Peter Linz Edition 4 Exercise 3.1 Question 13 (Page No. 76)
Find a regular expression for $L =$ {$vwv: v, w ∈${$a, b$}$^*, |v| =2$}.

Find a regular expression for $L =$ {$vwv: v, w ∈${$a, b$}$^*, |v| =2$}.

Naveen Kumar 3

239 views

Naveen Kumar 3 asked Mar 31, 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