menu
search
Log In
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

Subjects

Recent questions and answers in Theory of Computation

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

Recent questions and answers in Theory of Computation

0 votes
2 answers
1
UGCNET-Oct2020-II: 56
Consider the following languages: $L_1=\{a^{\grave{z}^z} \mid \grave{Z} \text{ is an integer} \}$ $L_2=\{a^{z\grave{z}} \mid \grave{Z} \geq 0\}$ $L_3=\{ \omega \omega \mid \omega \epsilon \{a,b\}^*\}$ Which of the languages is(are) regular? Choose the correct answer from the options given below: $L_1$ and $L_2$ only $L_1$ and $L_3$ only $L_1$ only $L_2$ only
Consider the following languages: $L_1=\{a^{\grave{z}^z} \mid \grave{Z} \text{ is an integer} \}$ $L_2=\{a^{z\grave{z}} \mid \grave{Z} \geq 0\}$ $L_3=\{ \omega \omega \mid \omega \epsilon \{a,b\}^*\}$ Which of the languages is(are) regular? Choose the correct answer from the options given below: $L_1$ and $L_2$ only $L_1$ and $L_3$ only $L_1$ only $L_2$ only
answered 1 day ago in Theory of Computation Joey 83 views
0 votes
2 answers
2
UGCNET-Oct2020-II: 57
Which of the following grammars is(are) ambiguous? $s \rightarrow ss \mid asb \mid bsa \mid \lambda$ $s \rightarrow asbs \mid bsas \mid \lambda$ $s \rightarrow aAB \\ A \rightarrow bBb \\ B \rightarrow A \mid \lambda \text{ where } \lambda \text{ denotes empty string}$ Choose the ... options given below: $(a)$ and $(c)$ only $(b)$ only $(b)$ and $(c)$ only $(a)$ and $(b)$ only
Which of the following grammars is(are) ambiguous? $s \rightarrow ss \mid asb \mid bsa \mid \lambda$ $s \rightarrow asbs \mid bsas \mid \lambda$ $s \rightarrow aAB \\ A \rightarrow bBb \\ B \rightarrow A \mid \lambda \text{ where } \lambda \text{ denotes empty string}$ Choose the correct answer from the options given below: $(a)$ and $(c)$ only $(b)$ only $(b)$ and $(c)$ only $(a)$ and $(b)$ only
answered 1 day ago in Theory of Computation Joey 92 views
1 vote
2 answers
3
Michael Sipser Edition 3 Exercise 5 Question 33 (Page No. 241)
Consider the problem of determining whether a $PDA$ accepts some string of the form $\{ww \mid w \in \{0,1\}^{\ast} \}$ . Use the computation history method to show that this problem is undecidable.
Consider the problem of determining whether a $PDA$ accepts some string of the form $\{ww \mid w \in \{0,1\}^{\ast} \}$ . Use the computation history method to show that this problem is undecidable.
answered 4 days ago in Theory of Computation Anshu Rathore 194 views
29 votes
5 answers
4
GATE2016-2-16
The number of states in the minimum sized DFA that accepts the language defined by the regular expression. $(0+1)^{*} (0+1) (0+1)^{*}$ is ________.
The number of states in the minimum sized DFA that accepts the language defined by the regular expression. $(0+1)^{*} (0+1) (0+1)^{*}$ is ________.
answered 4 days ago in Theory of Computation StoneHeart 7.5k views
27 votes
6 answers
5
GATE2015-2-53
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.
answered 4 days ago in Theory of Computation StoneHeart 7k views
51 votes
11 answers
6
GATE2015-1-52
Consider the DFAs $M$ and $N$ given above. The number of states in a minimal DFA that accept the language $L(M) \cap L(N)$ is_____________.
Consider the DFAs $M$ and $N$ given above. The number of states in a minimal DFA that accept the language $L(M) \cap L(N)$ is_____________.
answered 4 days ago in Theory of Computation StoneHeart 7.7k views
36 votes
4 answers
8
GATE2008-10
Which of the following are decidable? Whether the intersection of two regular languages is infinite Whether a given context-free language is regular Whether two push-down automata accept the same language Whether a given grammar is context-free I and II I and IV II and III II and IV
Which of the following are decidable? Whether the intersection of two regular languages is infinite Whether a given context-free language is regular Whether two push-down automata accept the same language Whether a given grammar is context-free I and II I and IV II and III II and IV
answered 6 days ago in Theory of Computation Surya_Dev Chaturvedi 7.5k views
20 votes
3 answers
9
GATE2008-9
Which of the following is true for the language $\left\{ a^p \mid p \text{ is a prime } \right \}?$ It is not accepted by a Turing Machine It is regular but not context-free It is context-free but not regular It is neither regular nor context-free, but accepted by a Turing machine
Which of the following is true for the language $\left\{ a^p \mid p \text{ is a prime } \right \}?$ It is not accepted by a Turing Machine It is regular but not context-free It is context-free but not regular It is neither regular nor context-free, but accepted by a Turing machine
answered 6 days ago in Theory of Computation Surya_Dev Chaturvedi 4.4k views
2 votes
1 answer
10
context free language
Show that the language L={xy∣|x|=|y|,x≠y} is context free. Do not give links plz explain in simple manner
Show that the language L={xy∣|x|=|y|,x≠y} is context free. Do not give links plz explain in simple manner
answered 6 days ago in Theory of Computation pragyak26 1.1k views
15 votes
3 answers
11
GATE1999-1.5
Context-free languages are closed under: Union, intersection Union, Kleene closure Intersection, complement Complement, Kleene closure
Context-free languages are closed under: Union, intersection Union, Kleene closure Intersection, complement Complement, Kleene closure
answered Jan 13 in Theory of Computation ankit3009 4.1k views
34 votes
3 answers
12
GATE1996-2.9
Define a context free languages $L \in \{0, 1\}^*$, $\text{init} (L) = \{u \mid uv \in L$ for some $v$ in $\{0, 1\}^*\}$ ( in other words, $\text{init}(L)$ is the set of prefixes of $L$ ... null string the set of all binary strings with exactly one more $0$ than the number of $1$'s or one more $1$ than the number of $0$'s None of the above
Define a context free languages $L \in \{0, 1\}^*$, $\text{init} (L) = \{u \mid uv \in L$ for some $v$ in $\{0, 1\}^*\}$ ( in other words, $\text{init}(L)$ is the set of prefixes of $L$ ... null string the set of all binary strings with exactly one more $0$ than the number of $1$'s or one more $1$ than the number of $0$'s None of the above
answered Jan 13 in Theory of Computation ankit3009 6.1k views
26 votes
6 answers
13
GATE1995-2.20
Which of the following definitions below generate the same language as $L$, where $L=\{x^ny^n \text{ such that } n\geq 1 \}$? $E \rightarrow xEy\mid xy$ $x y \mid (x^+xyy^+$) $x^+y^+$ I only I and II II and III II only
Which of the following definitions below generate the same language as $L$, where $L=\{x^ny^n \text{ such that } n\geq 1 \}$? $E \rightarrow xEy\mid xy$ $x y \mid (x^+xyy^+$) $x^+y^+$ I only I and II II and III II only
answered Jan 13 in Theory of Computation ankit3009 5.2k views
0 votes
2 answers
14
Deterministic Finite Automata ( DFA)
Construct a DFA over Σ=(a,b) so that it accepts all strings where 1) 2nd symbol from the right is 'a' 2) 3rd symbol from the right is 'a'
Construct a DFA over Σ=(a,b) so that it accepts all strings where 1) 2nd symbol from the right is 'a' 2) 3rd symbol from the right is 'a'
answered Jan 13 in Theory of Computation Dharmesh Dubey 432 views
18 votes
3 answers
15
GATE2006-IT-4
In the context-free grammar below, $S$ is the start symbol, $a$ and $b$ are terminals, and $\epsilon$ denotes the empty string $S \rightarrow aSa \mid bSb \mid a \mid b \mid \epsilon$ Which of the following strings is NOT generated by the grammar? $aaaa$ $baba$ $abba$ $babaaabab$
In the context-free grammar below, $S$ is the start symbol, $a$ and $b$ are terminals, and $\epsilon$ denotes the empty string $S \rightarrow aSa \mid bSb \mid a \mid b \mid \epsilon$ Which of the following strings is NOT generated by the grammar? $aaaa$ $baba$ $abba$ $babaaabab$
answered Jan 10 in Theory of Computation StoneHeart 1.6k views
6 votes
4 answers
16
TOC SAMPLE PRACTICE
Determine the minimum height of parse tree in CNF for terminal string of length w, which is constructed by using CFG G (a) log2|w|+1 (b) log2|w| (c) log2|w|−1 (d) None of these
Determine the minimum height of parse tree in CNF for terminal string of length w, which is constructed by using CFG G (a) log2|w|+1 (b) log2|w| (c) log2|w|−1 (d) None of these
answered Jan 10 in Theory of Computation StoneHeart 1.9k views
1 vote
1 answer
17
pda self doubt
The language accepted by a DPDA with a final state is more compared to the DPDA with empty stack. DPDA with empty stack accepts LR(0) grammar. Can someone explain in depth/or give good reference links?
The language accepted by a DPDA with a final state is more compared to the DPDA with empty stack. DPDA with empty stack accepts LR(0) grammar. Can someone explain in depth/or give good reference links?
answered Jan 9 in Theory of Computation reboot 187 views
35 votes
6 answers
18
GATE2005-53
Consider the machine $M$: The language recognized by $M$ is: $\left\{ w \in \{a, b\}^* \text{ | every a in $w$ is followed by exactly two $b$'s} \right\}$ $\left\{w \in \{a, b\}^* \text{ | every a in $w$ is followed by at least two $b$'s} \right\}$ ... $ contains the substring $abb$'} \right\}$ $\left\{w \in \{a, b\}^* \text{ | $w$ does not contain $aa$' as a substring} \right\}$
Consider the machine $M$: The language recognized by $M$ is: $\left\{ w \in \{a, b\}^* \text{ | every a in $w$ is followed by exactly two $b$'s} \right\}$ $\left\{w \in \{a, b\}^* \text{ | every a in $w$ is followed by at least two $b$'s} \right\}$ ... $ contains the substring $abb$'} \right\}$ $\left\{w \in \{a, b\}^* \text{ | $w$ does not contain $aa$' as a substring} \right\}$
answered Jan 3 in Theory of Computation Ram13may 5.5k views
1 vote
2 answers
19
NIELIT 2017 DEC Scientific Assistant A - Section B: 35
$\left (0+ \varepsilon \right) \left (1+ \varepsilon \right)$ represents : $\left \{0,1,01,\varepsilon \right \}$ $\left \{0,1,\varepsilon \right \}$ $\left \{0,1,01, 11, 00 ,10,\varepsilon \right \}$ $\left \{0,1, \right \}$
$\left (0+ \varepsilon \right) \left (1+ \varepsilon \right)$ represents : $\left \{0,1,01,\varepsilon \right \}$ $\left \{0,1,\varepsilon \right \}$ $\left \{0,1,01, 11, 00 ,10,\varepsilon \right \}$ $\left \{0,1, \right \}$
answered Jan 3 in Theory of Computation Ram13may 261 views
0 votes
2 answers
20
UGCNET-Oct2020-II: 28
Let $L_1$ and $L_2$ be languages over $\Sigma = \{a,b\}$ represented by the regular expressions $(a^* +b)^*$ and $(a+b)^*$ respectively. Which of the following is true with respect to the two languages? $L_1 \subset L_2$ $L_2 \subset L_1$ $L_1 = L_2$ $L_1 \cap L_2 = \phi$
Let $L_1$ and $L_2$ be languages over $\Sigma = \{a,b\}$ represented by the regular expressions $(a^* +b)^*$ and $(a+b)^*$ respectively. Which of the following is true with respect to the two languages? $L_1 \subset L_2$ $L_2 \subset L_1$ $L_1 = L_2$ $L_1 \cap L_2 = \phi$
answered Jan 3 in Theory of Computation Ram13may 148 views
0 votes
2 answers
21
NIELIT 2016 MAR Scientist C - Section C: 32
Two finite state machines are said to be equivalent if they have same number of states have same number of edges have same number of states and edges recognize same set of tokens
Two finite state machines are said to be equivalent if they have same number of states have same number of edges have same number of states and edges recognize same set of tokens
answered Jan 3 in Theory of Computation Ram13may 178 views
1 vote
2 answers
22
UGCNET-Oct2020-II: 29
Which of the following statements is true? The union of two context free languages is context free The intersection of two context free languages is context free The complement of a context free language is context free If a language is context free, it can always be accepted by a deterministic pushdown automaton
Which of the following statements is true? The union of two context free languages is context free The intersection of two context free languages is context free The complement of a context free language is context free If a language is context free, it can always be accepted by a deterministic pushdown automaton
answered Jan 3 in Theory of Computation Ram13may 96 views
4 votes
3 answers
24
MadeEasy Test Series: Theory Of Computation - Regular Languages
Consider the following statements: $S_1:\{(a^n)^m|n\leq m\geq0\}$ $S_2:\{a^nb^n|n\geq 1\} \cup \{a^nb^m|n \geq1,m \geq 1\} $ Which of the following is regular? $S_1$ only $S_2$ only Both Neither of the above
Consider the following statements: $S_1:\{(a^n)^m|n\leq m\geq0\}$ $S_2:\{a^nb^n|n\geq 1\} \cup \{a^nb^m|n \geq1,m \geq 1\} $ Which of the following is regular? $S_1$ only $S_2$ only Both Neither of the above
answered Jan 3 in Theory of Computation Joey 772 views
0 votes
1 answer
25
An Introduction to formal languages and automata
find grammar that generates L={a^nb^m:n>=0,m<n}
find grammar that generates L={a^nb^m:n>=0,m<n}
answered Jan 3 in Theory of Computation Joey 131 views
1 vote
2 answers
26
Recognize the language
If L be a language recognizable by a finite automata, then language from {L}={w such that w is prefix of v where v belongs to L},is a a. Regular Language b. Context Free language c. Context Sensitive Language d. Recursive Enumerable Language
If L be a language recognizable by a finite automata, then language from {L}={w such that w is prefix of v where v belongs to L},is a a. Regular Language b. Context Free language c. Context Sensitive Language d. Recursive Enumerable Language
answered Jan 3 in Theory of Computation Joey 1.3k views
1 vote
1 answer
27
Self doubt about relation between regular and linear grammar
If a grammar G is both left linear as well as right linear then,what should be the case a) G is always not regular b) G may or may not be regular c) something else
If a grammar G is both left linear as well as right linear then,what should be the case a) G is always not regular b) G may or may not be regular c) something else
answered Jan 2 in Theory of Computation StoneHeart 141 views
0 votes
1 answer
28
Linear grammar
Please follow the attachment how can we prove that the given language is not linear please explain?
Please follow the attachment how can we prove that the given language is not linear please explain?
answered Jan 2 in Theory of Computation StoneHeart 147 views
0 votes
2 answers
30
Concider the language L2
A. L2 is DCFL B. L2 is CFL but not DCFL C. L2 is not CFL D. None of these
A. L2 is DCFL B. L2 is CFL but not DCFL C. L2 is not CFL D. None of these
answered Dec 27, 2020 in Theory of Computation reboot 180 views
1 vote
1 answer
32
Identify the class of language
L2={a^i b^(i^2) } where I is natural no. Identify the class of language and it's complement...
L2={a^i b^(i^2) } where I is natural no. Identify the class of language and it's complement...
answered Dec 27, 2020 in Theory of Computation reboot 160 views
4 votes
2 answers
33
If L2 is DCFL ,how to draw its DPDA?
$L_1=\{(xy)^m(yz)^m\;,\;m\geq 1\}$ $L_2=\{a^mb^nc^k\;|\;m>n\;or\;m<n\}$ Which of the following is True? (a) $L_1$ is CFL, $L_2$ are DCFL (b) $L_1$ is DCFL, $L_2$ is CFL (c) Both $L_1$, $L_2$ are CFLs (d) Both $L_1$, $L_2$ are DCFLS
$L_1=\{(xy)^m(yz)^m\;,\;m\geq 1\}$ $L_2=\{a^mb^nc^k\;|\;m>n\;or\;m<n\}$ Which of the following is True? (a) $L_1$ is CFL, $L_2$ are DCFL (b) $L_1$ is DCFL, $L_2$ is CFL (c) Both $L_1$, $L_2$ are CFLs (d) Both $L_1$, $L_2$ are DCFLS
answered Dec 27, 2020 in Theory of Computation reboot 541 views
16 votes
5 answers
34
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.
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 Dec 26, 2020 in Theory of Computation reboot 2.7k views
31 votes
5 answers
35
GATE2006-IT-32
Let $L$ be a context-free language and $M$ a regular language. Then the language $L ∩ M$ is always regular never regular always a deterministic context-free language always a context-free language
Let $L$ be a context-free language and $M$ a regular language. Then the language $L ∩ M$ is always regular never regular always a deterministic context-free language always a context-free language
answered Dec 25, 2020 in Theory of Computation mani312 4.4k views
1 vote
2 answers
36
UGCNET-Oct2020-II: 27
Consider $L=L_1 \cap L_2$ where $L_1 = \{ 0^m 1^m 20^n 1^n \mid m,n \geq 0 \}$ $L_2 = \{0^m1^n2^k \mid m,n,k \geq 0 \}$ Then, the language $L$ is Recursively enumerable but not context free Regular Context free but not regular Not recursive
Consider $L=L_1 \cap L_2$ where $L_1 = \{ 0^m 1^m 20^n 1^n \mid m,n \geq 0 \}$ $L_2 = \{0^m1^n2^k \mid m,n,k \geq 0 \}$ Then, the language $L$ is Recursively enumerable but not context free Regular Context free but not regular Not recursive
answered Dec 24, 2020 in Theory of Computation Joey 171 views
81 votes
6 answers
37
GATE2014-2-36
Let $L_1=\{w\in\{0,1\}^*\mid w$ $\text{ has at least as many occurrences of }$ $(110)'$ $\text{s as }$ $(011)'$ $\text{s} \}$. Let $L_2=\{w \in\{0,1\}^*\ \mid w$ $ \text{ has at least as many occurrences of }$ $(000)'$ ... the following is TRUE? $L_1$ is regular but not $L_2$ $L_2$ is regular but not $L_1$ Both $L_1$ and $L_2$ are regular Neither $L_1$ nor $L_2$ are regular
Let $L_1=\{w\in\{0,1\}^*\mid w$ $\text{ has at least as many occurrences of }$ $(110)'$ $\text{s as }$ $(011)'$ $\text{s} \}$. Let $L_2=\{w \in\{0,1\}^*\ \mid w$ $ \text{ has at least as many occurrences of }$ $(000)'$ $\text{s as} $ ... one of the following is TRUE? $L_1$ is regular but not $L_2$ $L_2$ is regular but not $L_1$ Both $L_1$ and $L_2$ are regular Neither $L_1$ nor $L_2$ are regular
answered Dec 18, 2020 in Theory of Computation AJAY SENGAR 12.7k views
37 votes
3 answers
38
GATE1996-2.23
Consider the following state table for a sequential machine. The number of states in the minimized machine will be ... $4$ $3$ $2$ $1$
Consider the following state table for a sequential machine. The number of states in the minimized machine will be ... $4$ $3$ $2$ $1$
answered Dec 17, 2020 in Theory of Computation deepak_vatsalya 5.9k views
5 votes
5 answers
39
GATE 2020 CSE | Question: 32
Consider the following languages. $\begin{array}{ll} L_1= \{ wxyx \mid w,x,y \in (0+1)^{+} \} \\ L_2= \{xy \mid x,y \in (a+b)^{*}, \mid x \mid=\mid y \mid, x \neq y \} \end{array}$ ... context- free but not regular and $L_2$ is context-free. Neither $L_1$ nor $L_2$ is context- free. $L_1$ context- free but $L_2$ is not context-free.
Consider the following languages. $\begin{array}{ll} L_1= \{ wxyx \mid w,x,y \in (0+1)^{+} \} \\ L_2= \{xy \mid x,y \in (a+b)^{*}, \mid x \mid=\mid y \mid, x \neq y \} \end{array}$ Which one of the following is TRUE? $L_1$ ... $L_1$ context- free but not regular and $L_2$ is context-free. Neither $L_1$ nor $L_2$ is context- free. $L_1$ context- free but $L_2$ is not context-free.
answered Dec 15, 2020 in Theory of Computation Abhineet Singh 5.2k views
1 vote
4 answers
40
plz answer
the minimum number of states in the PDA accepting the language $L=\left\{a^n b^m \mid n>m;m,n>0 \right\}$ a) 2 b) 3 c) 4 d) 5
the minimum number of states in the PDA accepting the language $L=\left\{a^n b^m \mid n>m;m,n>0 \right\}$ a) 2 b) 3 c) 4 d) 5
answered Dec 10, 2020 in Theory of Computation Deepakk Poonia (Dee) 935 views
To see more, click for all the questions in this category.
Dark theme
Muffin by Hélio Chun
Thanks to Q2A
...