Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Filter
Profile
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
Questions by Mahesha999
0
votes
1
answer
1
Compexity of sum of complexity bounds
265
views
asked
Feb 2, 2017
Algorithms
algorithms
time-complexity
test-series
+
–
2
votes
0
answers
2
Working with Turing Machine transitions
500
views
asked
Jan 1, 2017
Theory of Computation
turing-machine
theory-of-computation
+
–
2
votes
1
answer
3
Working with PDA transitions
Either I dont understand PDA at all or this question is wrong or I am missing something very basic:
Either I dont understand PDA at all or this question is wrong or I am missing something very basic:
348
views
asked
Jan 1, 2017
Theory of Computation
pushdown-automata
+
–
3
votes
2
answers
4
Equivalent regex
Consider the regex: $(a+b)^*(a+b+\epsilon)a$ Which of the following is equivalent to above?: (a) $(a^*+b^*)^+(aa+ba)$ (b) $(\epsilon+a+b^*)^+a$ (c) $(a+b)^+(a+b+\epsilon)a$ (d) None of these
Consider the regex: $(a+b)^*(a+b+\epsilon)a$Which of the following is equivalent to above?:(a) $(a^*+b^*)^+(aa+ba)$(b) $(\epsilon+a+b^*)^+a$(c) $(a+b)^+(a+b+\epsilon)a$(d...
666
views
asked
Dec 26, 2016
Theory of Computation
regular-expression
+
–
1
votes
1
answer
5
Language accepted by NFA
Consider the NFA below: The above NFA acceptes all those binary strings which represents the decimal numbers and are a. divisible by 6 only b. dividible by 2 and 3 only c. divisible by 2 or 3 d. None of these
Consider the NFA below:The above NFA acceptes all those binary strings which represents the decimal numbers and area. divisible by 6 onlyb. dividible by 2 and 3 onlyc. di...
1.9k
views
asked
Dec 25, 2016
Theory of Computation
theory-of-computation
regular-language
+
–
10
votes
2
answers
6
Which of these languages are regular, CFL and CSL?
Consider the following statements: $L_1=\left\{\text{wxw$^R$|w$\in$(a,b)$^*$, x$\in$c }\right\}$ $L_2=\left\{\text{wy|w, y $\in$ (a,b)$^*$}\right\} $ ... free, $L_2$ and $L_3$ are regular and $L_4$ is context sensitive languages $L_1, L_4$ are context free, $L_2$ and $L_3$ is context sensitive languages
Consider the following statements:$L_1=\left\{\text{wxw$^R$|w$\in$(a,b)$^*$, x$\in$c }\right\}$$L_2=\left\{\text{wy|w, y $\in$ (a,b)$^*$}\right\} $$L_3=\left\{\text{zwz|w...
2.9k
views
asked
Dec 25, 2016
Theory of Computation
theory-of-computation
context-free-language
context-sensitive
+
–
3
votes
2
answers
7
How can I tell if these languages are context sensitive
How can I tell if languages $L_1$ and $L_2$ are Context Sensitive or not?
How can I tell if languages $L_1$ and $L_2$ are Context Sensitive or not?
973
views
asked
Dec 25, 2016
Theory of Computation
theory-of-computation
context-sensitive
+
–
1
votes
2
answers
8
Which one of the following languages is regular
2.1k
views
asked
Dec 25, 2016
Theory of Computation
theory-of-computation
regular-expression
+
–
0
votes
1
answer
9
DFA accepting (0+1)*01(0+1)*01(0+1)*
1.7k
views
asked
Dec 25, 2016
Theory of Computation
theory-of-computation
+
–
2
votes
1
answer
10
Intersection of two context free languages
Does the below problem makes any sense? And if yes what is its answer? How?
Does the below problem makes any sense? And if yes what is its answer? How?
1.5k
views
asked
Dec 24, 2016
2
votes
1
answer
11
How is this language context free?
How below language is context free? I am not able to imagine what could be the behaviour of the PDA accepting this language. Can anyone give a hint? $L=\{\omega:2n_a(\omega)\leq n_b(\omega)\leq 3n_a(\omega)\}$
How below language is context free? I am not able to imagine what could be the behaviour of the PDA accepting this language. Can anyone give a hint?$L=\{\omega:2n_a(\omeg...
300
views
asked
Dec 24, 2016
Theory of Computation
theory-of-computation
context-free-language
+
–
2
votes
1
answer
12
Why can't linear bounded automata accept an empty string?
The linear bounded automata (LBA) is defined as follows: A linear bounded automata is a nondeterministic Turing machine $M=(Q,\Sigma,\Gamma,\delta,q_0,\square,F)$ (as in the definition of TM) with the restriction that ... explains why LBA cannot accept empty string (which is why CSG does not have lambda production). Can anyone explain?
The linear bounded automata (LBA) is defined as follows:A linear bounded automata is a nondeterministic Turing machine $M=(Q,\Sigma,\Gamma,\delta,q_0,\square,F)$ (as in t...
1.5k
views
asked
Nov 20, 2016
Theory of Computation
theory-of-computation
context-sensitive
+
–
1
votes
1
answer
13
Addersg
Which of the following is/are true S1: parallel adder may consist of both half adder and full adder S2: serial adder consists of only full adders
Which of the following is/are trueS1: parallel adder may consist of both half adder and full adderS2: serial adder consists of only full adders
308
views
asked
Nov 2, 2016
0
votes
1
answer
14
Comment on (R,*) group / commutative / monoid
Which of the following true about (R,*)? 1) Group but not commutative 2) A commutative group 3) Not a semigroup 4) Not a monoid
Which of the following true about (R,*)?1) Group but not commutative2) A commutative group3) Not a semigroup4) Not a monoid
1.6k
views
asked
Jan 24, 2015
Set Theory & Algebra
set-theory&algebra
group-theory
+
–
0
votes
1
answer
15
Understanding Singularity, Triviality, consistency, uniqueness of solutions of linear system
I was solving problems on deciding whether the given system of linear equations with three unknowns have trivial unique solution, non trivial unique solution, non trivial infinite solutions or no solution ... solutions? For singular A, are there infinite non-trivial solutions or unique non-trivial solution?
I was solving problems on deciding whether the given system of linear equations with three unknowns have trivial unique solution, non trivial unique solution, non trivial...
5.9k
views
asked
Dec 7, 2014
1
votes
1
answer
16
Factor of determinant with identical row
How the following fact applies to determinants (I came across it while solving problems): Consider A is a n× n matrix, the elements of which are real (or complex) polynomials in x. If r rows of the determinant become identical when x ... is collapsing of rows of matrix (into one row) with order of its factors. Am I missing some stupid fact here?
How the following fact applies to determinants (I came across it while solving problems):Consider A is a n× n matrix, the elements of which are real (or complex) po...
1.9k
views
asked
Dec 3, 2014
Linear Algebra
matrix
linear-algebra
polynomials
+
–
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register