Recent questions and answers in Theory of Computation

Recent questions and answers in Theory of Computation

0 votes

1 answer

1

Given language L = (0+1)*0^n, define a DFA with as few states as possible.
Given language L = (0+1)*0^n, define a DFA with as few states as possible with n > 0.

thedrift611 answered in Theory of Computation May 3

37 views

1 vote

0 answers

2

Self doubt about CFG to CNF conversion.
I am still having some doubts when it comes to Context-Free Grammar to Chomsky Normal Form conversion. Here is what I did for the following CFG: $S \rightarrow bXb \ |\ bS \ |\ \epsilon\ |\ aSdSc$ $X \rightarrow aX \ |\ Xtt$ ... $H \rightarrow b$ $A \rightarrow a$ $D \rightarrow d$ $C \rightarrow c$ Did I do this correctly?

HenryAsks21 asked in Theory of Computation May 3

45 views

1 vote

0 answers

3

Self Doubt about Construction of CFG
I am trying to construct a CFG for this following langauge: L = $\{0^i 1^j | i \neq j \ and \ i, j > 0\}$, this is what I came up with: $ S \rightarrow A \ | \ B $ $A \rightarrow 0A1 \ |\ A1 \ |\ 011$ ... strings that we can have: s = {011, 00111, 001, 00011, ...} and it worked. So, my question is, is this correct CFG for this particular L?

HenryAsks21 asked in Theory of Computation Apr 30

21 views

0 votes

0 answers

4

Need Solution manual
Where can I get the solution manual for An Introduction to Formal Languages and Automata by peter linz for the back exercises?

tusharb asked in Theory of Computation Apr 19

33 views

1 vote

1 answer

5

NIELIT 2022 Jan Scientist B | Section B | Question: 43
Consider the following types of languages: $\text{L1}:$ Regular, $\text{L2}:$ Context-free, $\text{L3}:$ Recursive, $\text{L4}:$ Recursively enumerable. Which of the following is/are $\text{TRUE}$ ? $\text{L3}' \cup \text{L4}$ is recursively ... and $\text{III}$ only $\text{I}$ and $\text{IV}$ only $\text{I, II}$ and $\text{III}$ only

Aditya_ answered in Theory of Computation Apr 14

74 views

0 votes

0 answers

6

How to tackle regular expression to e-NFA conversion with multiple Kleene stars?

HenryAsks21 asked in Theory of Computation Apr 7

52 views

5 votes

4 answers

7

ISI2015-PCB-CS-5a
Construct two nonregular languages $L_1$ and $L_2$ such that $L_1 \cup L_2$ is regular. Prove that the languages $L_1$ and $L_2$ constructed above are nonregular and $L_1 \cup L_2$ is regular.

s_dr_13 answered in Theory of Computation Apr 6

1.1k views

2 votes

3 answers

8

CMI2019-A-1
Let $L_{1}:=\{a^{n}b^{m}\mid m,n\geq 0\: \text{and}\: m\geq n\}$ and $L_{2}:=\{a^{n}b^{m}\mid m,n\geq 0\: \text{and}\: m < n\}.$ The language $L_{1}\cup L_{2}$ is: regular, but not context-free context-free, but not regular both regular and context-free neither regular nor context-free

s_dr_13 answered in Theory of Computation Apr 6

514 views

34 votes

4 answers

9

GATE CSE 2000 | Question: 1.5
Let $L$ denote the languages generated by the grammar $S \to 0S0 \mid 00$. Which of the following is TRUE? $L = 0^+$ $L$ is regular but not $0^+$ $L$ is context free but not regular $L$ is not context free

0xprateek answered in Theory of Computation Apr 3

7.9k views

0 votes

0 answers

10

Convert the following regular expressions to NFA.
Convert the following regular expression (0+11)0*1 to NFA with e-transitions using the procedure given on pg. 66-67 Theorem 1.54 (Lemma 1.55) of the Introduction to Theory of Computation 3rd edition book by Michael Sipser. I followed ... Kleene star is added individually like 0*, how would we illustrate this? This was my approach for just 0*1 part:

HenryAsks21 asked in Theory of Computation Mar 30

163 views

0 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)

amitraj123 answered in Theory of Computation Mar 27

115 views

0 votes

0 answers

12

Minimal DFA
What will be the minimal DFA for $\left \{a^{n} :n mod 3 =0 \right \}\cup \left \{a^{n} :n mod 5 =1 \right \}$

ankit-saha asked in Theory of Computation Mar 24

77 views

1 vote

2 answers

13

Theory of Computation
"A DFA can simulate NFA" Anyone, please explain this statement in detail.

Nobin Sahu answered in Theory of Computation Mar 20

105 views

0 votes

0 answers

14

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 >0 \right \} \cup \left \{ ab{a}'' : n\geq 0 \right \}$

ankit-saha asked in Theory of Computation Mar 19

65 views

0 votes

2 answers

15

For any language, if the union of both is regular, then are those languages regular languages as well?

yuyutsu answered in Theory of Computation Mar 19

139 views

1 vote

2 answers

16

NIELIT 2016 MAR Scientist B - Section C: 25
Regarding power of recognition of language, which of the following statements is false? Non deterministic finite-state automata are equivalent to deterministic finite-state automata. Non-deterministic push-down automata are equivalent to ... to deterministic push-down automata. Multi-tape Turing Machines are equivalent to Single-tape Turing Machines.

33 answered in Theory of Computation Mar 16

by 33

816 views

3 votes

2 answers

17

NIELIT 2016 DEC Scientist B (CS) - Section B: 46
$(00+01+10)(0+1)^*$ represents Strings not starting with $11$ Strings of odd length Strings starting with $00$ Strings of even length

s_dr_13 answered in Theory of Computation Mar 14

561 views

0 votes

0 answers

18

Show that if L is regular, so is L ∪ {a}, for all a ∈ Σ.

Abhim1811 asked in Theory of Computation Mar 3

114 views

0 votes

2 answers

19

Regular Expression
can anyone help me with regular expression for- a)set of all strings with equal number of 0s and 1s such that no prefix has 2 more than 0s than 1s nor 2 more than 1's than 0's. b) set of all strings of 0s and 1s whose number of 0s is divisible by 5 and whose number of 1's is even.

wa_tle answered in Theory of Computation Mar 1

by wa_tle

3.6k views

0 votes

1 answer

20

What is the significances of extended transition function?
What is the significance of the extended transition function?

22 answered in Theory of Computation Mar 1

by 22

258 views

0 votes

0 answers

21

INTRODUCTION TO Automata Theory, Languages, and Computation by JOHN E. HOPCROFT
Design e - NF A for accepting decimal numbers

wa_tle asked in Theory of Computation Feb 27

by wa_tle

56 views

0 votes

0 answers

22

Epsilon NFA to DFA conversion
Convert the given epsilon NFA to minimal DFA https://gateoverflow.in/?qa=blob&qa_blobid=10553865129760839637

ambikesh_ak27 asked in Theory of Computation Feb 27

by ambikesh_ak27

101 views

9 votes

4 answers

23

GATE CSE 2021 Set 2 | Question: 47
Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string $\epsilon$ is divisible by three. $(0+1(01^*0)^*1)^*$ $(0+11+10(1+00)^*01)^*$ $(0^*(1(01^*0)^*1)^*)^*$ $(0+11+11(1+00)^*00)^*$

kathan2021 answered in Theory of Computation Feb 22

4.2k views

1 vote

1 answer

24

NPTEL Assignment
Let L={w| w has even length and odd number of 0’s}. Which of the following words is in L* (Kleen Closure of L). 0000 010101 111101 010 Answer Is Given 0000

Kabir5454 answered in Theory of Computation Feb 16

159 views

2 votes

2 answers

25

GATE CSE 2022 | Question: 13
Which of the following statements is/are $\text{TRUE}?$ Every subset of a recursively enumerable language is recursive. If a language $\textit{L}$ and its complement $\overline{\textit{L}}$ are both recursively enumerable, then $\textit{L}$ must be recursive. ... $\textit{L}_{1} \cap \textit{L}_{2}$ must be deterministic context-free.

Deepak Poonia answered in Theory of Computation Feb 16

by Deepak Poonia

928 views

3 votes

2 answers

26

GATE CSE 2022 | Question: 38
Consider the following languages: $L_{1} = \{ ww | w \in \{a,b\}^{\ast} \}$ $L_{2} = \{a^{n} b^{n} c^{m} | m,n \geq 0 \}$ $L_{3} = \{a^{m} b^{n} c^{n} | m,n \geq 0 \}$ Which of the following statements is/are $\text{FALSE}?$ ... $L_{2}$ is context-free. $L_{2}, L_{3}$ and $L_{2} \cap L_{3}$ all are context-free. Neither $L_{1}$ nor its complement is context-free.

Deepak Poonia answered in Theory of Computation Feb 15

by Deepak Poonia

841 views

3 votes

2 answers

27

GATE CSE 2022 | Question: 36
Which of the following is/are undecidable? Given two Turing machines $\textit{M}_{1}$ and $\textit{M}_{2},$ decide if $\textit{L(M}_{1}) = \textit{L(M}_{2}).$ Given a Turing machine $\textit{M},$ decide if $\textit{L(M)}$ is ... $\textit{M},$ decide if $\textit{M}$ takes more than $1073$ steps on every string.

Deepak Poonia answered in Theory of Computation Feb 15

by Deepak Poonia

646 views

4 votes

2 answers

28

GATE CSE 2022 | Question: 37
Consider the following languages: $L_{1} = \{ a^{n} wa^{n} | w \in \{a,b\}^{\ast}\}$ $L_{2} = \{wxw^{R} | w, x \in \{a,b\}^{*}, |w|, |x| > 0 \}$ Note that $w^{R}$ is the reversal of the string $w.$ Which of the following is/are ... $L_{2}$ are context-free. $L_{1}$ is regular and $L_{2}$ is context-free. $L_{1}$ and $L_{2}$ are context-free but not regular.

Deepak Poonia answered in Theory of Computation Feb 15

by Deepak Poonia

675 views

4 votes

2 answers

29

GATE CSE 2022 | Question: 2
Which one of the following regular expressions correctly represents the language of the finite automaton given below? $ab^{\ast}bab^{\ast} + ba^{\ast}aba^{\ast}$ $(ab^{\ast}b)^{\ast}ab^{\ast} + (ba^{\ast}a)^{\ast} ba^{\ast}$ $(ab^{\ast}b + ba^{\ast}a)^{\ast} (a^{\ast} + b^{\ast})$ $(ba^{\ast}a + ab^{\ast}b)^{\ast} (ab^{\ast} + ba^{\ast})$

Deepak Poonia answered in Theory of Computation Feb 15

by Deepak Poonia

1.1k views

29 votes

3 answers

30

GATE CSE 2014 Set 1 | Question: 35
Let $L$ be a language and $\bar{L}$ be its complement. Which one of the following is NOT a viable possibility? Neither $L$ nor $\bar{L}$ is recursively enumerable $(r.e.)$. One of $L$ and $\bar{L}$ is r.e. but not recursive; the other is not r.e. Both $L$ and $\bar{L}$ are r.e. but not recursive. Both $L$ and $\bar{L}$ are recursive.

bhargavprajapati answered in Theory of Computation Feb 3

by bhargavprajapati

6.1k views

0 votes

1 answer

31

Context Sensitive Grammars
Is the following CSG for a^n b^n c^n correct? S->aSbC|abc Cb->bC C->c If not please explain why?

girish13 answered in Theory of Computation Feb 1

172 views

0 votes

2 answers

32

Self Doubt
Could anyone please explain various tricks to find out wheather the given context free Grammar is ambiguous or not in an easier way?

aaa 1 answered in Theory of Computation Jan 31

by aaa 1

145 views

1 vote

1 answer

33

regular languages - TOC
Which of the following languages is/are regular?

amitraj123 answered in Theory of Computation Jan 29

138 views

0 votes

1 answer

34

pumping length - TOC
What is meant by ‘pumping length’ and how can we find it?

aaa 1 answered in Theory of Computation Jan 29

by aaa 1

100 views

3 votes

3 answers

35

Reducibility
If L1 is reducible to L2 and L1 is recursively enumerable then what can we say about L2?

ShouvikSVK answered in Theory of Computation Jan 28

338 views

1 vote

1 answer

36

countability
if a language is not recursively enumerable, then is it uncountable language? I believe every language over ∑ is subset of ∑* which is a countable set and as subset of countable set is countable therefore every language itself is countable whether it is recursively enumerable or not.

arks answered in Theory of Computation Jan 23

by arks

200 views

2 votes

2 answers

37

Countability
A language in NOT - RE is un-countably infinite. true or false?

arks answered in Theory of Computation Jan 23

by arks

837 views

1 vote

1 answer

38

Made Easy Test Series
Consider L = {w011w | w ∈ (o+1)*}. Find minimum number of states that are required in DFA (L). Found this question in Made Easy Test Series and I think the question is incorrect, as the language is not regular. The solution of this question given by Made Easy ... the given solution to be true L should be, L = {w011x | w,x ∈ (o+1)*}. Request you all to provide your comments.

amitraj123 answered in Theory of Computation Jan 22

136 views

1 vote

2 answers

39

DCFL - TOC
Is the following language a DCFL? Please explain your reasoning.

Chandrabhan Vishwa 1 answered in Theory of Computation Jan 21

by Chandrabhan Vishwa 1

189 views

0 votes

1 answer

40

parse tree - context-free grammars - TOC
Given a CFG and a string, what is the relation between the number of leftmost derivations, the number of rightmost derivations and the number of parse trees?

Aditya_ answered in Theory of Computation Jan 21

222 views

To see more, click for all the questions in this category.

Follow @gateoverflow

Recent questions and answers in Theory of Computation

Search GATE Overflow for GATE CSE