Recent questions and answers in Theory of Computation

0 votes

0 answers

1

self made
I know it is weird to ask but we know that we can convert NFA TO DFA but is it any procedure to convert DFA to NFA.

asked 1 hour ago in Theory of Computation by Divyanshum29 (123 points) | 4 views

0 votes

0 answers

2

UGCNET-NOV2017-III-51

asked 2 hours ago in Theory of Computation by Roma_nagpal (115 points) | 3 views

0 votes

0 answers

3

UGCNET-NOV2017-III-63
Consider the following languages : L1 = {am bn | m ≠ n} L2 = {am bn | m = 2n+1} L3 = {am bn | m ≠ 2n} Which one of the following statement is correct ? Only L1 and L2 are context free languages Only L1 and L3 are context free languages Only L2 and L3 are context free languages L1, L2 and L3 are context free languages

asked 2 hours ago in Theory of Computation by Roma_nagpal (115 points) | 4 views

0 votes

0 answers

4

#DFA #TOC #theoryofcomputation
How to construct an automata with even number of a's OR odd number of b's?

asked 10 hours ago in Theory of Computation by aditykansara (11 points) | 11 views

0 votes

3 answers

5

Regular Expressions
does this R.E satisfies for the language - no 2 a's come together where £=(a,b)? (b*ab*)*+b*

answered 1 day ago in Theory of Computation by Prince Sindhiya Junior (699 points) | 36 views

0 votes

1 answer

6

DCFL or Not
$\left \{ a^{m+n}b^{m+n}c^{n}|m,n\geq 1 \right \}$ $\left \{ a^{m+n}b^{m+n}c^{k} |m,n,k\geq 1\right \}$ $\left \{ a^{m+n}b^{m+k}c^{n+k} |m,n,k\geq 1\right \}$ Which one DCFL, CFL or CSL?

answered 1 day ago in Theory of Computation by Prince Sindhiya Junior (699 points) | 88 views

0 votes

0 answers

7

self doubt 22/6
true or false complent of cfl is decidable ? complement of recursive language is decidable? complement of REL is decidable?

asked 2 days ago in Theory of Computation by eyeamgj Active (2.4k points) | 19 views

+16 votes

4 answers

8

GATE2018-52
Given a language $L$, define $L^i$ as follows: $$L^0 = \{ \varepsilon \}$$ $$L^i = L^{i-1} \bullet L \text{ for all } I >0$$ The order of a language $L$ is defined as the smallest $k$ such that $L^k = L^{k+1}$. Consider the language $L_1$ (over alphabet O) accepted by the following automaton. The order of $L_1$ is ____

answered 2 days ago in Theory of Computation by Sushant kaushal (53 points) | 2.2k views

0 votes

0 answers

9

Moore machine
Can Moore machine be minimized without converting into mealy machine?Is minimization possible directly?

asked 3 days ago in Theory of Computation by Harshitha 123 (87 points) | 15 views

0 votes

0 answers

10

Semi-decidability Vs Undecidability
Let L1 and L2 be 2 languages generated by an Unrestricted Grammar. I know that none of the following are decidable. But which of them are semi-decidable and which are Undecidable? 1. Whether L1 is Finite? 2. Whether L1 is Regular? 3. Whether L1 is Equivalent to ... complete? 8. Whether L1 is a subset of L2? 9. Whether (∑* - L1) is finite? 10. Whether L1 is Empty?

asked 4 days ago in Theory of Computation by Balaji Jegan Active (1.1k points) | 79 views

+1 vote

2 answers

11

[Doubt] Conversion of finite automata to regular expression

answered 4 days ago in Theory of Computation by krmanish043 (23 points) | 226 views

+4 votes

2 answers

12

TIFR2018-B-14
Define the language $INFINITE_{DFA}\equiv \{(A)\mid A \text{ is a DFA and } L(A) \text{ is an infinite language}\},$ where $(A)$ denotes the description of the deterministic finite automata (DFA).Then which of the following about ... . It is Turing decidable (recursive). It is Turing recognizable but not decidable. Its complement is Turing recognizable but it is not decidable.

answered 4 days ago in Theory of Computation by Kushagra Chatterjee Loyal (8.2k points) | 220 views

0 votes

0 answers

13

ISI CSB 2018 Question number C4.
C4. Construct a Deterministic Finite Automaton (DFA) to accept L={s1s2.....sn | n >=1; for each i=1,2,.....n, si € {0,1}, and the number of 1's minus the number of 0's in s1s2....si is zero,one or two} For example, the DFA should accept 11 or 1100 but not 1110.

asked 4 days ago in Theory of Computation by Anwesha Kashyap (13 points) | 18 views

0 votes

0 answers

14

Regular Expressions
What is the language produced by.... null*(denoted by phi) doubt from youtube video here

asked 5 days ago in Theory of Computation by Kirandas R (67 points) | 35 views

+18 votes

3 answers

15

GATE1997-3.4
Given $\Sigma=\{a,b\}$, which one of the following sets is not countable? Set of all strings over $\Sigma$ Set of all languages over $\Sigma$ Set of all regular languages over $\Sigma$ Set of all languages over $\Sigma$ accepted by Turing machines

answered 5 days ago in Theory of Computation by Radha mohan Junior (565 points) | 1.6k views

0 votes

0 answers

16

Decidable
All $P$, $NP$ and $NPC$ problems are turing decidable problems. $CFLs$ are in $NP$ area and $CFL's$ are not closed under intersection and complementation. So does it mean that $CFL's$ are undecidable under intersection and complementation. If $CFL$ is undecidable on intersection and complementation then how $NP$ problems can be turing decidable?

asked 6 days ago in Theory of Computation by !KARAN (329 points) | 19 views

0 votes

0 answers

17

Test series
Can someone explain this problem? Thanks in advance

asked Jun 17 in Theory of Computation by Kalpataru Bose (337 points) | 40 views

0 votes

0 answers

18

Peter linz
Input alphabet {a,b} give a dfa for L= w1a w2 where |w1|>=3,|w2|<=5. (Unit 2 exercise 6 problem)

asked Jun 16 in Theory of Computation by Harshitha 123 (87 points) | 30 views

0 votes

0 answers

19

Finite Automata
Whenever it is mentioned to derive minimal finite automata. We should go with DFA or NFA?

asked Jun 15 in Theory of Computation by jaisyking (7 points) | 29 views

0 votes

0 answers

20

Decision properties of finite automata
Is equivalence problem decidable problem or not?

asked Jun 15 in Theory of Computation by Harshitha 123 (87 points) | 25 views

0 votes

1 answer

21

Decidable or not
Now define D , the diagonal set of strings: $D=\left \{ w\epsilon \Sigma ^{*} \right \}$ where $w$ is not in $f\left ( w \right )$ Call the correspondence $f$ is countable set $\Sigma ^{*}$ For example $f\left ( \varepsilon \right )=L_{0}$ ,i.e. ... ( 1 \right )=L_{2}$ for all even length string of infinite language etc. Now, the question is 1) is D countable? 2) is D decidable?

answered Jun 15 in Theory of Computation by koki (51 points) | 24 views

+16 votes

4 answers

22

GATE2005-IT-4
Let $L$ be a regular language and $M$ be a context-free language, both over the alphabet $Σ$. Let $L^c$ and $M^c$ denote the complements of $L$ and $M$ respectively. Which of the following statements about the language $L^c\cup M^c$ is TRUE? It is necessarily regular but not necessarily context-free. It is necessarily context-free. It is necessarily non-regular. None of the above

answered Jun 15 in Theory of Computation by suryaprakash Junior (747 points) | 1.3k views

+9 votes

5 answers

23

GATE1998-3b
Give a regular expression for the set of binary strings where every $0$ is immediately followed by exactly $k$ $1$'s and preceded by at least $k$ $1$’s ($k$ is a fixed integer)

answered Jun 14 in Theory of Computation by Radha mohan Junior (565 points) | 1k views

0 votes

0 answers

24

Theory of computation
What is grid automata (m+1)(n+1) state calculation? (For some question asked from Peter Linz unit -2 exercise 2(d) the answer is given as" it is like grid automata and to calculate number of states we can use (m+1)(n+1) if we require m a's and n b's" and the question is "all strings with at least one 'a' and exactly 2b's" )

asked Jun 14 in Theory of Computation by Harshitha 123 (87 points) | 27 views

0 votes

1 answer

25

GATE CS Mock 2018 (Set -2)
Let δ denote the transition function and α denoted the extended transition function of the ε-NFA whose transition table is given below: Which of the following option is correct? A) α (q1,aba) is {q0, q2} B) null reachable states are {q0, q1, q2}B C) α (q3,bab) is {q0, q1, q2, q3} D) None of these

answered Jun 14 in Theory of Computation by Kajal Khobragade Active (1.3k points) | 73 views

+9 votes

4 answers

26

GATE1991-17,a
Show that the Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class of regular languages.

answered Jun 14 in Theory of Computation by suryaprakash Junior (747 points) | 503 views

+2 votes

2 answers

27

Grammars
Is epsilon(empty string) a pallindrome?

answered Jun 14 in Theory of Computation by PiratedVirus (167 points) | 37 views

+1 vote

0 answers

28

ISRO CS 17
Consider the following statements about the context free grammar G = {S-->SS , S-->ab , S-->ba , S-->^} I. G is ambiguous II. G produces all strings with equal number of a's and b's III. G can be accepted by a deterministic PDA. Which combination below expresses all ... ? A) I only B) I and III C) II and II D) All I,II,III In a answer key shown answer D but II is not right.

asked Jun 13 in Theory of Computation by Nikhil Patil (371 points) | 42 views

0 votes

0 answers

29

Regular Expression DFA
Regular Expression for this DFA: (a) (b + aa)* ab(a + b)* (b) b*a (ab*a)* b(a + b)* (c) Both (a) and (b) (d) b* ab(a + b)*

asked Jun 13 in Theory of Computation by Sanjay Sharma Boss (48.2k points) | 53 views

0 votes

2 answers

30

Toc DFA

answered Jun 12 in Theory of Computation by Prateek Raghuvanshi Active (3.9k points) | 65 views

0 votes

1 answer

31

Gate1994
The number of substrings(of all lengths inclusive) that can be formed from character string of length n is a)n b)n^2 c)n(n-1)/2 d)(n(n+1)/2)+1

answered Jun 12 in Theory of Computation by Shaik Masthan Active (2.5k points) | 75 views

+1 vote

3 answers

32

Theory of computation

answered Jun 12 in Theory of Computation by Prince Sindhiya Junior (699 points) | 71 views

0 votes

0 answers

33

Minimal dfa
How many states will be present in L={w/(n(a) + (2 n(b)mod 3)) lessthan 2} ? (I got 7 states is that correct)

asked Jun 12 in Theory of Computation by Harshitha 123 (87 points) | 32 views

0 votes

2 answers

34

Can aabbaabbbbbbbbaaaa be generate by (a|b)*

answered Jun 11 in Theory of Computation by Aman Janko (21 points) | 30 views

0 votes

1 answer

35

Equivalence classes
Consider a regular language L over Σ={0,1} such that L contains every string which ends with "0". The number of equivalence classes in L is ______.

answered Jun 11 in Theory of Computation by aakashpreetam (331 points) | 143 views

+2 votes

2 answers

36

UGCNET-Nov2017-iii-23
Finite state machine can recognize langauge generated by _________. A. Only context free grammar B. Only context sensitive grammar C. Only regular grammar D. Any unambiguous grammar

answered Jun 11 in Theory of Computation by Deepakk Poonia (Dee) Boss (13.2k points) | 66 views

+1 vote

2 answers

37

UGCNET-Nov2017-iii-21
Pumping lemma for regular language is generally used for proving: A. Whether two given regular expressions are equivalent B. A given grammar is ambiguous C. A given grammar is regular D. A given grammar is not regular

answered Jun 11 in Theory of Computation by Deepakk Poonia (Dee) Boss (13.2k points) | 34 views

+1 vote

1 answer

38

UGCNET-Nov2017-iii-22
Which of the following problems is undecidable? A. To determine if two finite automata are equivalent B. Membership problem for context free grammar C. Finiteness problem for finite automata D. Ambiguity problem for context free grammar

answered Jun 11 in Theory of Computation by Prasanjeet Ghosh Active (1.3k points) | 34 views

0 votes

2 answers

39

Find the number of strings in finite automata:

answered Jun 11 in Theory of Computation by Kuldeep Tyagi (11 points) | 166 views

0 votes

1 answer

40

self made doubt
How to know that the language needs 1 stack or more than one stack in order to know about it is regular, context-free or not. example L1={$a^i b^j c^k│i<j<k$} L2={$a^i b^j c^k│i<j \ or \ k<j$} L3={$a^i b^j c^k│i<j \ and \ k<j$}

answered Jun 11 in Theory of Computation by Prateek Raghuvanshi Active (3.9k points) | 45 views

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

Recent questions and answers in Theory of Computation

Recent Posts

Recent Blog Comments