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 theoryofcomputation
0
votes
1
answer
Decidability Problem (Rice University pdf)
For the following language, state whether language is (I) recursive, (II) recursively enumerable but not recursive, or (III) not recursively enumerable. Prove your answer. $L_{11} = \{<M_{1}, M_2>  \text{ M}_1 \text{and M}_2 \text{ are two TMs}, \text{and } \epsilon \in L(M_1) \backslash L(M_2) \}$
asked
1 day
ago
in
Digital Logic
by
Mk Utkarsh
(
111
points)

29
views
theoryofcomputation
decidability
0
votes
0
answers
It is CFL or not
It is CFL or not $\{wa^n w^r \ w\ \in (a+b)^*, n>=0 \}$
asked
2 days
ago
in
Theory of Computation
by
Sandeep Verma
(
102
points)

17
views
theoryofcomputation
contextfreelanguages
+1
vote
1
answer
The language is context free or not
consider this language: L={(a^n b^n)^2 :n>=0} Is this context free?
asked
3 days
ago
in
Theory of Computation
by
Doraemon
(
139
points)

26
views
contextfreelanguages
theoryofcomputation
0
votes
1
answer
regular language and few statements
$L$ is a regular language over $\Sigma^*$ $X = \{ x x\ belongs\ to\ \Sigma^*, x\ is\ between\ n\ to\ 2n1\ \}$ $\exists w \in x, w \in L\ then\ L\ is\ infinite.$ $\exists, w >= 2n,\ w \in L\ then\ \exists x \in X$ Which one of the following statements are true ? (A) Only I (B) Only II (C) Both I and II (D) Neither I or II
asked
4 days
ago
in
Theory of Computation
by
KINGSLAYER
(
106
points)

11
views
#regularlanguage
theoryofcomputation
#testseries
gatebook
0
votes
1
answer
why L2 is not regular? [Source: Applied Course live session]
asked
5 days
ago
in
Theory of Computation
by
Sathuri Bharath
(
126
points)

30
views
theoryofcomputation
regularlanguages
0
votes
1
answer
PETER LINZDFA
The minimum number of states for these 2 languages: L1={w: (n(a)n(b)) mod 3=2} L2={w: (n(a)n(b)) mod 3=0} I am getting 9 for both of them .Please verify:)
asked
6 days
ago
in
Theory of Computation
by
Doraemon
(
139
points)

9
views
theoryofcomputation
peterlinz
0
votes
0
answers
Peter Linz Exercise 1.3 Question 12
Design a transducer to convert a binary string into octal. For example, the bit string 001101110 should produce the output 156. In this case, are we given only those binary strings whose lengths are multiples of 3? Are we reading the binary string in reverse or normally? Also, please provide the solution to this problem.
asked
6 days
ago
in
Theory of Computation
by
GATE_aspirant_2021
(
102
points)

5
views
theoryofcomputation
peterlinz
selfdoubt
0
votes
1
answer
Post correspondence is itself decision on decidability how then it is ambiguous
asked
6 days
ago
in
Theory of Computation
by
Anisha140197
(
102
points)

26
views
theoryofcomputation
0
votes
1
answer
Ambiguity of grammars
Consider the Language: L = {$a^{n}b^{n}c^{k}$, n,k ≥ 1} ⋃ {$a^{n}b^{k}c^{k}$, n,k≥ 1} Which is True? (a) All the Grammars generating L will be ambiguous. (b) There exists a G which is unambiguous. (c) Language L is unambiguous (d) None of the above
asked
Aug 13
in
Theory of Computation
by
Sambhrant Maurya
(
281
points)

8
views
theoryofcomputation
grammars
ambiguity
0
votes
2
answers
Relation between A,B and C
Let A= (a + b)* ab (a + b)*, B= a*b* and C= (a + b)*. Then the relation between A, B and C: A. A+B= C B. $A^{R}+B^{R}=C$ C. $A^{R}$+B= C D. None of these
asked
Aug 12
in
Theory of Computation
by
Sambhrant Maurya
(
281
points)

32
views
theoryofcomputation
regularlanguages
0
votes
1
answer
Deterministic FA
What are the number of final states in minimal DFA, where Σ= {a, b}, if every string starts with “aa” and length of string is not congruent to 0 (mod 4). A. 7 B. 6 C. 3 D. 5
asked
Aug 12
in
Theory of Computation
by
Sambhrant Maurya
(
281
points)

16
views
theoryofcomputation
finiteautomata
0
votes
1
answer
Family of Languages
The language of primes in unary is: Regular CFL CSL DCFL
asked
Aug 12
in
Theory of Computation
by
Sambhrant Maurya
(
281
points)

6
views
theoryofcomputation
languages
0
votes
0
answers
ACE Workbook  Finite automata and Regular Language
asked
Aug 11
in
Theory of Computation
by
user2525
(
1.6k
points)

5
views
theoryofcomputation
#regularlanguage
finiteautomata
0
votes
2
answers
Complement of Context Free Language
I have read that CFL is not closed under complementation. I read somewhere that complement of CFL is CSL. I am not sure if I remember it correctly. Answer is given as D here. Kindly clarify my doubt. Thank you.
asked
Aug 11
in
Theory of Computation
by
DukeThunders
(
208
points)

11
views
theoryofcomputation
0
votes
1
answer
Epsilon NFA doubt
Please show the approach. I am not fully aware of how delta star works. Does it mean applying epsilon *, a, epsilon * on qo state? Kindly explain. Thank you.
asked
Aug 11
in
Theory of Computation
by
DukeThunders
(
208
points)

6
views
theoryofcomputation
finiteautomata
0
votes
0
answers
Made Easy workbook  Finite Automata
While doing reversal of a Finite automata, we change the arrows and interchange the final and initial states. But if there are more than one final state in F.A. are we supposed to merge the final states into one final state and then do the reversal of the finite automata. Is it the correct procedure for reversal of finite automata wth multiple final states ?
asked
Aug 11
in
Theory of Computation
by
user2525
(
1.6k
points)

6
views
#regularlanguage
theoryofcomputation
finiteautomata
0
votes
1
answer
NFA with epsilon moves  Automata theory ( Testbook Test Series )
asked
Aug 11
in
Theory of Computation
by
user2525
(
1.6k
points)

9
views
theoryofcomputation
finiteautomata
#regularlanguage
+1
vote
1
answer
Regular Language  Theory of Computation
Which of the following are regular languages ? $wxw^R ( w ∈ (a,b)^* , x ∈ (a,b)^* )$ $wxw^R ( w ∈ (a,b)^* , x ∈ (a,b)^+ )$ $wxw^R ( w ∈ (a,b)^+ , x ∈ (a,b)^* )$ $wxw^R ( w ∈ (a,b)^+ , x ∈ (a,b)^+ )$ $wxw ( w ∈ (a,b)^* , x ∈ (a,b)^* )$ ... $wxw ( w ∈ (a,b)^+ , x ∈ (a,b)^* )$ $wxw ( w ∈ (a,b)^+ , x ∈ (a,b)^+ )$ Here $w^R$ is reversal of string $w$.
asked
Aug 9
in
Theory of Computation
by
user2525
(
1.6k
points)

13
views
theoryofcomputation
finiteautomata
#regularlanguage
0
votes
1
answer
Stanford Lagunita
Which of the following grammars produce regular languages? A → (A)/ε A → (A(/ε A → (B)/(BB) B → (CC)/(CCC) C → (DDD) D → () A→ aA/b A→ Aa/b A→ aaAb/ε A→ AAaab/ε A→ AAaab/aab
asked
Aug 9
in
Theory of Computation
by
Sambhrant Maurya
(
281
points)

7
views
theoryofcomputation
regularlanguages
regulargrammar
finiteautomata
0
votes
0
answers
ACE Test Series  Finite automata and regular language
asked
Aug 8
in
Theory of Computation
by
user2525
(
1.6k
points)

32
views
theoryofcomputation
finiteautomata
#regularlanguage
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
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
0
votes
1
answer
String generation
Identify from the following the string generated by following $ S→SS , $ $S \rightarrow \ (S_1, $ $ S_1→S) ,$ $S_1 \rightarrow ) $ A. $(( ) ( ) ))$ B. $((((( )))))) ($ C. $( ) ( ) ( ) ( ))$ D.$ (( ) ((( )) ( )))$
asked
Jul 31
in
Theory of Computation
by
kshubham538
(
162
points)

15
views
madeeasyworkbook
grammar
theoryofcomputation
0
votes
2
answers
Is my NFA correct for the question given below?if not then what will be
asked
Jul 28
in
Theory of Computation
by
shaktisingh
(
104
points)

13
views
theoryofcomputation
nfa
intersection
–1
vote
1
answer
Ambiguity related to Context free grammar
asked
Jul 28
in
Theory of Computation
by
kshubham538
(
162
points)

26
views
contextfreelanguages
grammar
theoryofcomputation
ambiguity
0
votes
1
answer
Context free grammar
asked
Jul 25
in
Theory of Computation
by
kshubham538
(
162
points)

22
views
madeeasyworkbook
contextfreelanguages
grammar
theoryofcomputation
0
votes
1
answer
REGULAR LANGUAGES
Is (a^n)* {where n is prime} Regular ??
asked
Jul 25
in
Theory of Computation
by
Ritabrata Dey
(
242
points)

32
views
theoryofcomputation
0
votes
1
answer
Identifying regular self doubt
How (a^n)* where n is prime is regular?
asked
Jul 22
in
Theory of Computation
by
Winner
(
120
points)

20
views
theoryofcomputation
0
votes
1
answer
Language recognition by DFA
asked
Jul 20
in
Theory of Computation
by
kshubham538
(
162
points)

6
views
#regularlanguage
theoryofcomputation
#dfa
0
votes
2
answers
Self Doubt: Why is "intersection with regular languages" closed for context free languages ?
asked
Jul 20
in
Theory of Computation
by
commenter commenter
(
126
points)

9
views
theoryofcomputation
contextfreelanguages
regular
0
votes
1
answer
Self Doubt: Theory of Computation
What is the difference between intersection and cross product of DFAs? Are they both same?
asked
Jul 20
in
Theory of Computation
by
commenter commenter
(
126
points)

20
views
theoryofcomputation
dfas
finiteautomata
0
votes
1
answer
Finiteautomata
asked
Jul 19
in
Theory of Computation
by
kshubham538
(
162
points)

8
views
theoryofcomputation
madeeasyworkbook
finiteautomata
#regularexpression
0
votes
0
answers
Theory of computation #pumping lemma #minimum pumping length
asked
Jul 19
in
Theory of Computation
by
misba
(
102
points)

12
views
theoryofcomputation
0
votes
1
answer
CFL or Not(Peter Linz)
Determine whether or not the following language is contextfree? $L = \{a^nww^Ra^n : n \geq0, w \in\{a,b\}^* \}$ This is the approach i am trying NPDA will have to make 2 choices It will have to find when sequence of $a$ finished and ... the stack. So all these comparision, NPDA is not doing at the same time. Hence it must be CFL Please check and comment if anything is wrong
asked
Jul 18
in
Theory of Computation
by
!KARAN
(
140
points)

6
views
theoryofcomputation
0
votes
2
answers
Regular grammar to string production
asked
Jul 17
in
Theory of Computation
by
kshubham538
(
162
points)

29
views
madeeasyworkbook
regular
grammar
theoryofcomputation
0
votes
1
answer
Regular production Grammar
Consider the production grammar S→AB  AS A→a  aA B→b Which of the following regular expressions corresponding to the production grammar?
asked
Jul 17
in
Theory of Computation
by
kshubham538
(
162
points)

9
views
#regularexpression
regular
grammar
theoryofcomputation
madeeasyworkbook
–1
vote
1
answer
Regular expression to finite automata
The regular expression for even number of zeroes is A. (1* 01* 01*)* B. (1* 001*)* C. 1* + (1* 01* 01*)* D. ((0 + 1)* 0(0 + 1)* 0(0 + 1)*)* Also draw the finite automata.
asked
Jul 17
in
Theory of Computation
by
kshubham538
(
162
points)

11
views
theoryofcomputation
madeeasyworkbook
#regularexpression
0
votes
1
answer
Finite automata to Regular Expression
The language recognized by the given finite automata is A. (aa + ∊) (b + ba) (bab)* B. (aab + ba) (bab)* C. (aab) (bab)* + (bab)* D. (aab) (∈ + (bab)*)*
asked
Jul 17
in
Theory of Computation
by
kshubham538
(
162
points)

11
views
#regularexpression
#regularlanguage
theoryofcomputation
finiteautomata
madeeasyworkbook
+1
vote
1
answer
Regular expression
Which of the following regular expression over {0,1} denotes the set of all strings not containing 100 as sub string A. 0* (1*0)* B. 0* 10 10* C. 0* 1* 01* D. 0* (10 + 1)*
asked
Jul 16
in
Theory of Computation
by
kshubham538
(
162
points)

8
views
theoryofcomputation
#gate
madeeasyworkbook
#regularlanguage
#regularexpression
Page:
1
2
next »
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
932
questions
596
answers
1,885
comments
81,474
users