Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Recent questions and answers in Theory of Computation
0
votes
0
answers
1
TOC doubt
How a language which is not recursively enumerable is uncountable,because as we know every language is a subset of sigma(input alphabet) star which is known to be countable? Please explain I am getting confused in this.
How a language which is not recursively enumerable is uncountable,because as we know every language is a subset of sigma(input alphabet) star which is known to be countab...
Himanshu555
asked
in
Theory of Computation
Aug 5
by
Himanshu555
17
views
0
votes
1
answer
2
Zeal Test Series 2019: Theory of Computation - Grammar
Consider the following statements. S1: An unambiguous left recursive grammar must be CLR(1). S2: A DCFG may or may not be LL(1). Select the correct option: 1.Both S1 and S2 are true. 2.Both S1 and S2 are false. 3. S1 is false and S2 is true. 4.S1 is true and S2 is false. According to me S1 false and S2 true but answer given 1
Consider the following statements. S1: An unambiguous left recursive grammar must be CLR(1). S2: A DCFG may or may not be LL(1). Select the correct option: 1.Both S1 and ...
manikantsharma
answered
in
Theory of Computation
Jul 31
by
manikantsharma
462
views
zeal
theory-of-computation
grammar
zeal2019
0
votes
2
answers
3
Grammar
Can set of terminal be empty in a grammar? Is epsilon (null string) counted as a terminal symbol?
Can set of terminal be empty in a grammar? Is epsilon (null string) counted as a terminal symbol?
manikantsharma
answered
in
Theory of Computation
Jul 31
by
manikantsharma
686
views
theory-of-computation
grammar
0
votes
1
answer
4
Self Doubt
$L=\{wa^nw^Rb^n\mid w\in \left \{ a,b \right \}^\ast ,n\geqslant 0\}$ Can anyone give me step by step solution that shows this is not CFL by pumping Lemma?
$L=\{wa^nw^Rb^n\mid w\in \left \{ a,b \right \}^\ast ,n\geqslant 0\}$ Can anyone give me step by step solution that shows this is not CFL by pumping Lemma?
ankitgupta.1729
answered
in
Theory of Computation
Jul 30
by
ankitgupta.1729
62
views
self-doubt
theory-of-computation
pumping-lemma
1
vote
0
answers
5
toc igate test series
equivalence of two regular language can be tested in (worst case)? polynomial time sub linear time exponential time poly logarithmic time
equivalence of two regular language can be tested in (worst case)? polynomial time sub linear time exponential time poly logarithmic time
jugnu1337
asked
in
Theory of Computation
Jul 27
by
jugnu1337
61
views
theory-of-computation
0
votes
1
answer
6
Igate Test Series
please explain all options with example
please explain all options with example
Kabir5454
answered
in
Theory of Computation
Jul 21
by
Kabir5454
63
views
decidability
closure-property
0
votes
1
answer
7
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?
Where can I get the solution manual for An Introduction to Formal Languages and Automata by peter linz for the back exercises?
Bikram 1
answered
in
Theory of Computation
Jul 21
by
Bikram 1
169
views
finite-automata
theory-of-computation
0
votes
0
answers
8
Self Doubt.
what is the difference between, r* and r^(*) can anyone please elaborate !
what is the difference between, r* and r^(*) can anyone please elaborate !
akash_chauhan
asked
in
Theory of Computation
Jul 20
by
akash_chauhan
77
views
theory-of-computation
regular-expression
finite-automata
0
votes
1
answer
9
Self Doubt
Is the diagonalization language (Ld) countable?
Is the diagonalization language (Ld) countable?
Kabir5454
answered
in
Theory of Computation
Jul 20
by
Kabir5454
134
views
theory-of-computation
self-doubt
0
votes
1
answer
10
Self Doubt
If for every RE there exist a TM that accepts it, is it possible that for 2 different RE languages there exists a single TM that accepts them?
If for every RE there exist a TM that accepts it, is it possible that for 2 different RE languages there exists a single TM that accepts them?
tanBit
answered
in
Theory of Computation
Jul 20
by
tanBit
69
views
theory-of-computation
self-doubt
0
votes
1
answer
11
Test Series
[email protected]
2022
Please explain the ans. Ans is (B)
Please explain the ans. Ans is (B)
Kabir5454
answered
in
Theory of Computation
Jul 20
by
Kabir5454
68
views
turing-machine
0
votes
1
answer
12
[email protected]
Test Series 2022
Please explain with simplified diagram the transition in the pda. Ans (d)
Please explain with simplified diagram the transition in the pda. Ans (d)
Aditya_
answered
in
Theory of Computation
Jul 18
by
Aditya_
54
views
pushdown-automata
2
votes
2
answers
13
Michael Sipser Edition 3 Exercise 1 Question 71 (Page No. 93)
Let $\sum = \{0,1\}$ Let $A=\{0^{k}u0^{k}|k\geq 1$ $\text{and}$ $u\in \sum^{*}\}.$ Show that $A$ is regular. Let $B=\{0^{k}1u0^{k}|k\geq 1$ $\text{and}$ $u\in \sum^{*}\}.$Show that $B$ is not regular.
Let $\sum = \{0,1\}$ Let $A=\{0^{k}u0^{k}|k\geq 1$ $\text{and}$ $u\in \sum^{*}\}.$ Show that $A$ is regular. Let $B=\{0^{k}1u0^{k}|k\geq 1$ $\text{and}$ $u\in \sum^{*}\}....
akash_chauhan
answered
in
Theory of Computation
Jul 18
by
akash_chauhan
261
views
michael-sipser
theory-of-computation
finite-automata
regular-language
proof
descriptive
0
votes
1
answer
14
Michael Sipser Edition 3 Exercise 2 Question 44 (Page No. 158)
If $A$ and $B$ are languages, define $A \diamond B = \{xy \mid x \in A\: \text{and}\: y \in B \;\text{and} \mid x \mid = \mid y \mid \}$. Show that if $A$ and $B$ are regular languages, then $A \diamond B$ is a CFL.
If $A$ and $B$ are languages, define $A \diamond B = \{xy \mid x \in A\: \text{and}\: y \in B \;\text{and} \mid x \mid = \mid y \mid \}$. Show that if $A$ and $B$ are reg...
akash_chauhan
answered
in
Theory of Computation
Jul 18
by
akash_chauhan
145
views
michael-sipser
theory-of-computation
regular-language
proof
1
vote
1
answer
15
identify language is regular or not L={wcw^r | w,c belongs to E*} E={a,b}
identify language is regular or not L={wcw^r | w,c belongs to E*} E={a,b} if yes then why please explain
identify language is regular or not L={wcw^r | w,c belongs to E*} E={a,b} if yes then why please explain
akash_chauhan
answered
in
Theory of Computation
Jul 17
by
akash_chauhan
97
views
theory-of-computation
regular-language
pumping-lemma
context-free-language
0
votes
1
answer
16
Theory of Computation
Steps to find the answer?
Steps to find the answer?
Vishal_kumar98
answered
in
Theory of Computation
Jul 17
by
Vishal_kumar98
100
views
theory-of-computation
ace-test-series
regular-expression
minimal-state-automata
0
votes
1
answer
17
Regular Expression
Identify whether the language is regular or not and plz justify the ans.
Identify whether the language is regular or not and plz justify the ans.
Kabir5454
answered
in
Theory of Computation
Jul 17
by
Kabir5454
69
views
theory-of-computation
regular-language
test-series
1
vote
0
answers
18
Theory of Computation, Regular language
Need help , to identify the regular languages
Need help , to identify the regular languages
Karishma Datt
asked
in
Theory of Computation
Jul 17
by
Karishma Datt
101
views
theory-of-computation
test-series
1
vote
1
answer
19
Michael Sipser Edition 3 Exercise 1 Question 20 (Page No. 86)
For each of the following languages, give two strings that are members and two strings that are not members-a total of four strings for each part. Assume the alphabet $Σ = \{a,b\}$ in all parts. $a^{*}b^{*}$ $a(ba)^{*}b$ ... $aba\cup bab$ $(\epsilon\cup a)b$ $(a\cup ba\cup bb)\Sigma^{*}$
For each of the following languages, give two strings that are members and two strings that are not members—a total of four strings for each part. Assume the alphabet $...
akash_chauhan
answered
in
Theory of Computation
Jul 16
by
akash_chauhan
659
views
michael-sipser
theory-of-computation
regular-language
regular-expression
0
votes
0
answers
20
Theory of computation
How to decide function is Homorphism.
How to decide function is Homorphism.
GateOverflow04
asked
in
Theory of Computation
Jul 16
by
GateOverflow04
66
views
theory-of-computation
ace-test-series
0
votes
1
answer
21
Context free language
Why the complement of a CFL is CSL?
Why the complement of a CFL is CSL?
Abhrajyoti00
answered
in
Theory of Computation
Jul 16
by
Abhrajyoti00
117
views
theory-of-computation
self-doubt
context-free-language
0
votes
0
answers
22
Theory Of Computation
please verify the answer I think BD on ‘b’ going on ‘BD’??
please verify the answer I think BD on ‘b’ going on ‘BD’??
GateOverflow04
asked
in
Theory of Computation
Jul 16
by
GateOverflow04
56
views
theory-of-computation
ace-test-series
1
vote
3
answers
23
[email protected]
2022
please explain it how to solve such question in exam Ans: 22
please explain it how to solve such question in exam Ans: 22
shishir__roy
answered
in
Theory of Computation
Jul 15
by
shishir__roy
132
views
theory-of-computation
numerical-answers
regular-expression
zeal
0
votes
2
answers
24
Draw a DFA (Deterministic Finite Automation) that has a total number of zeros in the string divisble by two and three.
Example: 11110100000111 should be accepted. There are 6 zeros. 6 is divisble by 2 and 3. This machine required at least six states.
ritik456
answered
in
Theory of Computation
Jul 11
by
ritik456
75
views
theory-of-computation
finite-automata
1
vote
2
answers
25
Draw a DFA (Deterministic Finite Automation) in which first two bits are the same as the last two bits
Examples of what works: 01101101101101 1011101010 1010 0101
ritik456
answered
in
Theory of Computation
Jul 11
by
ritik456
146
views
finite-automata
theory-of-computation
0
votes
1
answer
26
Draw a DFA (Deterministic Finite Automation) that has a its thrid to last digit as a 1
Examples that work: 100, 0000000101,110101010101 This DFA requires at least 8 states
Examples that work: 100, 0000000101,110101010101 This DFA requires at least 8 states
rohankrishan
asked
in
Theory of Computation
Jun 30
by
rohankrishan
57
views
theory-of-computation
finite-automata
1
vote
2
answers
27
why (a+b+c)*!= (a*+b*+c*) and why (a+b+c)* = (a*+b*+c*)*
From (a+b+c)* we can generate either a or b or c and kleene closure of that alphabet i.e a* or b* or c* which is same as (a*+b*+c*) .
From (a+b+c)* we can generate either a or b or c and kleene closure of that alphabet i.e a* or b* or c* which is same as (a*+b*+c*) .
Karishma Datt
asked
in
Theory of Computation
Jun 24
by
Karishma Datt
88
views
theory-of-computation
regular-expression
0
votes
1
answer
28
Dcfl union Regular not always dcfl?
$L=\{a^mb^n\mid m≠n\}∪{(a+b)^∗b(b+a)^*a(a+b)^∗}= \;\{a^mb^n\mid m<n\} \cup \{a^mb^n\mid m>n\} \cup (a+b)^*b(a+b)^*a(a+b)^*$ It is DCFL ∪ Regular, hence it should be DCFL, but not able to design DPDA, always it designed as NPDA. Can anybody made DPDA for $L$?
$L=\{a^mb^n\mid m≠n\}∪{(a+b)^∗b(b+a)^*a(a+b)^∗}= \;\{a^mb^n\mid m<n\} \cup \{a^mb^n\mid m>n\} \cup (a+b)^*b(a+b)^*a(a+b)^*$ It is DCFL ∪ Regular, hence it shoul...
juuniversity
asked
in
Theory of Computation
Jun 23
by
juuniversity
66
views
dcfl
context-free-language
theory-of-computation
0
votes
0
answers
29
construct a DFA of the language containing the set of all strings over {a, b} which accepts strings with length > 3 and the first digit from LHS is different from the third digit on the RHS
Ex. (baaab, babababa, aaabbaaabbb) Ex. (babab, abaaabb, aaaa, bbab)
Hamsho
asked
in
Theory of Computation
Jun 11
by
Hamsho
68
views
0
votes
0
answers
30
Construct equivalent DFA transaction table for the following NFA.
Construct equivalent DFA transaction table for the following NFA.
Construct equivalent DFA transaction table for the following NFA.
Subhrangsu
asked
in
Theory of Computation
May 29
by
Subhrangsu
94
views
theory-of-computation
finite-automata
0
votes
0
answers
31
Decidability and undecidability
How is equality problem for DCFL decidable?
How is equality problem for DCFL decidable?
sara02
asked
in
Theory of Computation
May 24
by
sara02
61
views
0
votes
1
answer
32
CMI 2021 Computer Science (A2)
Let L be the language over {a, b} that contains the same number of occurrences of a and b. Which of the following languages is regular? (a) L ∩ a∗b∗ (b) (L ∩ a∗b∗) ∪ a∗b∗ (c) L ∪ a∗b∗ (d) (L ∩ a∗b∗) ∪ b∗a My personal ... a*b* is regular and and L is regular. However L1 union/intersection L is not regular Could someone please explain this question in some detail ?
Let L be the language over {a, b} that contains the same number of occurrences of a and b. Which of the following languages is regular? (a) L ∩ a∗b∗ (b) (L ∩ a∗...
ChayAdhiraj
asked
in
Theory of Computation
May 19
by
ChayAdhiraj
115
views
theory-of-computation
doubt
0
votes
0
answers
33
Number of states in a DFA that accepts the language over the alphabet{0,1} where words start and end with a '1', have even length and where any 0 in the word is immediately followed by at least a 1.
Examples of accepted words: 1011, 101101, 1111 Example of non-accepted words: 101, 1001, 010 The solution says the min-DFA contains 5 states but I could only do it in 4. ...
koushriek
asked
in
Theory of Computation
May 19
by
koushriek
187
views
theory-of-computation
finite-automata
1
vote
0
answers
34
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?
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 \ |\ b...
HenryAsks21
asked
in
Theory of Computation
May 3
by
HenryAsks21
93
views
theory-of-computation
conjunctive-normal-form
0
votes
1
answer
35
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.
Given language L = (0+1)*0^n, define a DFA with as few states as possible with n > 0.
kthegarty
asked
in
Theory of Computation
Apr 30
by
kthegarty
106
views
theory-of-computation
finite-automata
1
vote
0
answers
36
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?
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 \ri...
HenryAsks21
asked
in
Theory of Computation
Apr 30
by
HenryAsks21
54
views
theory-of-computation
context-free-language
Help get things started by
asking a question
.
Subscribe to GATE CSE 2023 Test Series
Subscribe to GO Classes for GATE CSE 2023
Quick search syntax
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 Posts
IIT GATE Admission Online Form 2023
All about M.Tech. and Research Admissions at IITP
IIT JAM Admission Online Form 2023
All about M.Tech. and Research Admissions at IITGn
All about M.Tech. and Research Admissions at IITR
Subjects
All categories
General Aptitude
(2.4k)
Engineering Mathematics
(8.8k)
Digital Logic
(3.2k)
Programming and DS
(5.6k)
Algorithms
(4.4k)
Theory of Computation
(6.5k)
Compiler Design
(2.2k)
Operating System
(4.8k)
Databases
(4.4k)
CO and Architecture
(3.6k)
Computer Networks
(4.4k)
Non GATE
(1.2k)
Others
(2.3k)
Admissions
(644)
Exam Queries
(837)
Tier 1 Placement Questions
(17)
Job Queries
(72)
Projects
(9)
Unknown Category
(852)
Recent questions and answers in Theory of Computation
Recent Blog Comments
It is now added under "Others/Site Issues" now.
A category should be added for reporting bugs and...
Added.
Please add this to the list.
you should focus on coding if you're ok with your...