search
Log In

Recent questions and answers in Theory of Computation

0 votes
2 answers
1
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
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
29 votes
5 answers
4
27 votes
6 answers
5
51 votes
11 answers
6
36 votes
4 answers
8
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
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
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
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
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
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
18 votes
3 answers
15
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
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
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
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
0 votes
2 answers
20
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
1 vote
2 answers
22
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
0 votes
1 answer
25
1 vote
2 answers
26
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
0 votes
1 answer
28
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
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
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
$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
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
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
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
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
5 votes
5 answers
39
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
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.
...