Awesome q2a theme
Ask us anything
Toggle navigation
Email or Username
Password
Remember
Login
Register

I forgot my password
All Activity
Questions
Unanswered
Tags
Categories
Users
Ask a Question
Recent questions tagged #toc
0
votes
0
answers
Describe a nondeterministic pda with three states that accept the language 0^n 1^m {n<M<2n} by empty stack
asked
4 days
ago
in
Theory of Computation
by
paraskk
(
102
points)

2
views
#toc
0
votes
0
answers
Positive closures of any regular language will not contain epsilon?(True or False)
asked
4 days
ago
in
Theory of Computation
by
Chirag Shilwant
(
102
points)

4
views
#toc
regularlanguages
+1
vote
1
answer
How atleast become 2^n?
Given An arbitary nondeterministic finite automation with N states,the maximum numer of states in an equivalent minimized DFA is atleast?
asked
4 days
ago
in
Theory of Computation
by
bibin765
(
103
points)

7
views
#toc
#dfa
nfa
#gate2001
#gate
+1
vote
1
answer
Which of the following are regular languages? [Source: Applied Course live session]
asked
5 days
ago
in
Theory of Computation
by
Sathuri Bharath
(
126
points)

18
views
#toc
regularlanguages
+1
vote
1
answer
checking if given languages are regular or not
Consider the following languages. Which one of the following statements is true ? (A) L1 is regular, L2 is non regular (B) L1 is non regular, L2 is regular (C) L1 is regular, L2 is regular (D) L1 is non regular, L2 is non regular My ... string and if it is, we can prove that L1 is regular, but how can L2 be regular as that order needs to be maintained!
asked
5 days
ago
in
Theory of Computation
by
KINGSLAYER
(
106
points)

38
views
gatebook
regularlanguages
#testseries
#toc
0
votes
1
answer
Context free language
Is the given language CFL or not? Σ*L={a^n b^n a^n n>=1}
asked
Aug 14
in
Theory of Computation
by
kshubham538
(
162
points)

16
views
#toc
cfg
contextfreelanguages
0
votes
0
answers
Gateoverflow question  doubt
https://gateoverflow.in/311001/deletionofuselesssymbolsfromagrammarselfdoubt In the above question aren’t we supposed to delete the production A → b because at the end after removing the useless symbols, A is unreachable from the start symbol S. So, wont be the answer S → a only after removing useless symbols ?
asked
Aug 12
in
Theory of Computation
by
user2525
(
1.6k
points)

14
views
#toc
cfg
0
votes
0
answers
Number of derivations and height of parse tree in GNF
asked
Aug 11
in
Theory of Computation
by
DukeThunders
(
208
points)

12
views
#toc
0
votes
0
answers
Which of these machines can accept ambiguous grammar?
asked
Aug 11
in
Theory of Computation
by
DukeThunders
(
208
points)

8
views
#toc
0
votes
1
answer
Regular expression doubt
Please explain the solution. Thank you.
asked
Aug 11
in
Theory of Computation
by
DukeThunders
(
208
points)

6
views
#toc
0
votes
1
answer
Number of states in DFA
1. A minimal DFA accepting the language $L = \{ww ∈ (a,b,c) ^∗\}$, the number of a’s, b’s and c’s in w are divisible by $2, 3$ and $4$ respectively has ________ number of states Answer is given as 24 but isn’t 12 (lcm of 2,3,4) enough?
asked
Aug 10
in
Theory of Computation
by
DukeThunders
(
208
points)

20
views
#toc
#dfa
0
votes
0
answers
DFA Practice question
Q1: Construct the minimal finite automata that accept all the strings of 0's & 1's is where the integer equivalent is congruent to 1(mod 4). What is the no. of states in minimal finite automata? Q2: Construct the minimal finite automata that accept all ... to 5(mod 8) has __________ no. of states. Please show the minimal DFA of at least one of the questions. Thank you.
asked
Aug 10
in
Theory of Computation
by
DukeThunders
(
208
points)

4
views
#toc
#dfadesign
0
votes
0
answers
TOC practice question on CFG
L = {$x^{a}y^{a}$: a ≥ 1} I. $L^{3}$ is context free. II. ⌈√L⌉ is not context free. Which of the following is correct? (a) I only (b) II only (c) Both I and II (d) None of the above The answer is given A) What are the languages represented by $L^{3}$ and ⌈√L⌉?
asked
Aug 10
in
Theory of Computation
by
DukeThunders
(
208
points)

4
views
#toc
0
votes
1
answer
DCFG Self Doubt
if $a^nb^n$ is DCFL the is $(a^nb^n)$* DCFL?
asked
Aug 9
in
Theory of Computation
by
aditi19
(
134
points)

17
views
#toc
contextfreelanguages
contextfreelanguage
kleeneclosure
0
votes
1
answer
TOC self doubt practice question
Consider two statements: S1: Every regular language has regular proper subset. S2: If L1 and L2 are nonregular, then L1⋃ L2 is also notregular. (a) Both are True (b) Both are False (c) S1 → True, S2 → False (d) S1 → False, S2 → True I am getting both as true ... >= 0 } L1 ∪ L2 = { a^ib^jc^k i=j or j=k } ← CFL but not regular. Please explain where I am wrong.
asked
Aug 9
in
Theory of Computation
by
DukeThunders
(
208
points)

9
views
#toc
0
votes
2
answers
Language L = {an bn w  n ≥ 0, w ∈ {c, d}*, w = n} is
asked
Aug 9
in
Theory of Computation
by
DukeThunders
(
208
points)

6
views
#toc
0
votes
1
answer
DFA complement doubt
If D is a DFA having N states which accepts L and D' is a DFA having M states that accepts L' (complement of L), can it be always said that N=M? What about NFA?
asked
Aug 9
in
Theory of Computation
by
DukeThunders
(
208
points)

5
views
#toc
#dfadesign
0
votes
0
answers
Stanford Compilers course
Which of the following grammar(s) produce regular languages?
asked
Aug 9
in
Theory of Computation
by
siva_skl
(
102
points)

15
views
compiler
#toc
grammar
#regularlanguage
0
votes
1
answer
which of the following strings are in L1 U L2?
asked
Aug 6
in
Theory of Computation
by
Sathuri Bharath
(
126
points)

10
views
#toc
#language
0
votes
1
answer
gate 2014 toc self doubt
https://gateoverflow.in/1994/gate2014235 in this question can’t we directly apply rices theorem we can have a Tyes for languages with 2014 length input and Tno for Σ* since Tyes subset Tno it shouldnt be recursively enumerable . could someone elaborate where i am wrong?
asked
Aug 6
in
Theory of Computation
by
TUSHAR_BHATT
(
110
points)

13
views
#toc
#decidability
#ricestheorem
0
votes
0
answers
DFA question
I think the language accepted by the FA is (a+b)*. Then complement of it is phi. So shouldn’t there be one state? Which doesn’t accepting anything? Can I say that the FA which accepts phi is a single state with no final state? It accepts nothing. Can I say the FA which accepts only 0 length string has a single state where the the intial state is final state? Thank you.
asked
Aug 5
in
Theory of Computation
by
DukeThunders
(
208
points)

19
views
#toc
#dfadesign
0
votes
1
answer
CFL CSL Question
14. Consider the following languages: L1= {a^n b^n (n ≥ 0)} L2= Complement (L1) Choose appropriate options regarding languages L1 and L2 (a) L1& L2 are context free (b) L1 is CFL but L2 is RL (c) L1 is CFL and L2 is CSL (d) None Answer is ... , then L2 will be CSL since complement of NCFL is CSL. Then the answer comes out to be C. Please help in clarifying my doubt. Thank you.
asked
Aug 5
in
Theory of Computation
by
DukeThunders
(
208
points)

29
views
contextsensitivelanguages
cfland
theoryofcomputation
#toc
0
votes
2
answers
Regular Expression question
Kindly share the solution. Thank you.
asked
Aug 5
in
Theory of Computation
by
DukeThunders
(
208
points)

8
views
#toc
theoryofcomputation
0
votes
1
answer
TOC: why n and m are unrelated in square of a language?
asked
Aug 5
in
Theory of Computation
by
Sathuri Bharath
(
126
points)

13
views
#toc
#language
0
votes
1
answer
Context free grammar: string derivation
Consider the following CFG S→aAbBC  abB A→bBd  ∈ B→eBf  g C→f How many derivative steps required to derive the string abegff using the above grammar when start symbol S is available?
asked
Jul 31
in
Theory of Computation
by
kshubham538
(
162
points)

5
views
cfg
madeeasyworkbook
theoryofcomputation
#toc
+1
vote
1
answer
Doubt in TOC, Design of DFA
How to design DFA for the query “ Strings starting with ‘ab’ and ending with ‘ab’ over the alphabet {a,b} ”.
asked
Jul 31
in
Theory of Computation
by
Lakshmikanta
(
109
points)

23
views
#toc
#dfadesign
0
votes
2
answers
Regular Expression?
asked
Jul 30
in
Theory of Computation
by
Rajeevkr
(
115
points)

13
views
#toc
0
votes
1
answer
Finite state machine
asked
Jul 30
in
Theory of Computation
by
Rajeevkr
(
115
points)

4
views
#toc
0
votes
1
answer
What will be the answer and how?
asked
Jul 28
in
Theory of Computation
by
Rajeevkr
(
115
points)

17
views
#toc
0
votes
1
answer
Minimum states in Finite Automata (TOC)
In gate, if we are asked to find the minimum states of finite automata, then should we solve the question by assuming DFA or NFA? For example: What is the minimum number of states in Finite Automata required to print a string of length n. Using DFA: We will get n+2 states. Using NFA: We will get n+1 states.
asked
Jul 27
in
Theory of Computation
by
nadeshseen
(
106
points)

19
views
#toc
0
votes
1
answer
No. of states in minimum DFA for given Regular Expression
asked
Jul 22
in
Theory of Computation
by
kshubham538
(
162
points)

21
views
#regularlanguage
#dfa
#toc
#madeeasyworkbook
0
votes
1
answer
How many states are there in a minimum state deterministic finite automata accepting L={ba,baa}?
asked
Jul 15
in
Theory of Computation
by
kshubham538
(
162
points)

21
views
#toc
#dfa
#regularlanguage
#madeeasyworkbook
To see more, click for the
full list of questions
or
popular tags
.
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
931
questions
593
answers
1,873
comments
81,472
users