search
Log In

Recent questions tagged identify-class-language

4 votes
3 answers
1
Let $L_1$ be a regular language and $L_2$ be a context-free language. Which of the following languages is/are context-free? $L_1 \cap \overline{L_2} \\$ $\overline{\overline{L_1} \cup \overline{L_2}} \\$ $L_1 \cup (L_2 \cup \overline{L_2}) \\$ $(L_1 \cap L_2) \cup (\overline{L_1} \cap L_2)$
asked Feb 18 in Theory of Computation Arjun 959 views
0 votes
1 answer
2
Match $\text{List I}$ with $\text{List II}$ $L_R:$ Regular language, $LCF$: Context free language $L_{REC}:$ Recursive langauge, $L_{RE}$ ... options given below: $A-II, B-III, C-I$ $A-III, B-I, C-II$ $A-I, B-II, C-III$ $A-II, B-I, C-III$
asked Nov 20, 2020 in Theory of Computation jothee 125 views
1 vote
1 answer
3
0 votes
1 answer
4
1 vote
1 answer
6
Regarding power of recognition of language, which of the following statements is false? Non deterministic finite-state automata are equivalent to deterministic finite-state automata. Non-deterministic push-down automata are equivalent to deterministic push-down ... are equivalent to deterministic push-down automata. Multi-tape Turing Machines are equivalent to Single-tape Turing Machines.
asked Mar 31, 2020 in Theory of Computation Lakshman Patel RJIT 449 views
1 vote
3 answers
7
Which of the following statement is true? Deterministic context free language are closed under complement. Deterministic context free language are not closed under Union. Deterministic context free language are closed under intersection with regular set. All of the options
asked Mar 30, 2020 in Theory of Computation Lakshman Patel RJIT 522 views
1 vote
3 answers
8
Which of the following is a correct hierarchical relationships of the following where $L_1$: set of languages accepted by NFA $L_2$: set of languages accepted by DFA $L_3$: set of languages accepted by DPDA $L_4$: set of languages accepted by NPDA $L_5$: set of ... $L_2\subset L_1\subset L_3\subset L_4\subset L_5\subset L_6$ $L_1\subset L_2\subset L_3\subset L_4\subset L_6\subset L_5$
asked Mar 30, 2020 in Theory of Computation Lakshman Patel RJIT 503 views
0 votes
1 answer
9
Given the following two statements: $L=\{w\mid n_{a}(w)=n_{b}(w)\}$ is deterministic context free language, but not linear. $L=\{a^{n}b^{n}\} \cup \{a^{n}b^{2n} \}$ is linear, but not deterministic context free language. Which of the following options is correct? Both (A) and (B) are false. Both (A) and (B) are true. (A) is true, (B) is false. (A) is false, (B) is true.
asked Mar 24, 2020 in Theory of Computation jothee 195 views
12 votes
6 answers
10
Consider the language $L = \{a^{n}\mid n \geq 0\} \cup \{a^{n}b^{n}\mid n \geq 0\}$ and the following statements. $L$ is deterministic context-free. $L$ is context-free but not deterministic context-free. $L$ is not $LL(k)$ for any $k$. Which of the above statements is/are TRUE? Ⅰ only Ⅱ only Ⅰ and Ⅲ only Ⅲ only
asked Feb 12, 2020 in Theory of Computation Arjun 7.8k views
10 votes
3 answers
11
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.
asked Feb 12, 2020 in Theory of Computation Arjun 7.2k views
1 vote
1 answer
12
$L=\{wxyw|w,x,y\in (a+b)^+ \}$ $L$ is ? Regular Deterministic CFL Non-deterministic CFL CSL
asked Mar 28, 2019 in Theory of Computation Verma Ashish 109 views
1 vote
2 answers
13
If $L = \Bigl \{ x \mid x \in \{ a, b, c \}^*, \text{The length of $x$ is a square } \Bigr \}$ then $L$ is Regular Recursive but not context free Context Free but not regular None of the above
asked Mar 24, 2019 in Theory of Computation aditi19 224 views
1 vote
1 answer
14
Let Σ = {a, b}. For a word w ∈ Σ* , let na(x) denote the number of a’s in w and let nb(x) denote the number of b’s in w. Consider the following language: L := {xy | x, y ∈ Σ* , na(x) = nb(y)} What can we say about L? L is regular, but not context-free. L is context-free, but not regular. L is Σ*. None of these.
asked Jan 26, 2019 in Theory of Computation jatin khachane 1 146 views
0 votes
1 answer
15
Please suggest me in briefly for revision . How to we test regular,dcfl,cfl,recursive and recursive enumeranle. Eg say if we can find the pattern it's regular. Please help
asked Jan 24, 2019 in Theory of Computation Mayankprakash 100 views
3 votes
1 answer
16
Consider the infinite two-dimensional grid G={(m,n)| m and n are integers} Every point in G has 4 neighbors, North, South, East, and West, obtained by varying m or n by 1. Starting at the origin (0,0), a string of command letters N, S, E, W generates a ... a closed path. Which of the following statements is TRUE? i) L is Regular. ii) L is context free. iii) L complement is context free. Thanks!
asked Jan 22, 2019 in Theory of Computation Abhipsa 160 views
1 vote
0 answers
17
Consider the following language over ∑={0,1} $L_{1} = \left \{ a^{\left \lfloor \frac{m}{n} \right \rfloor}| m,n \geq 1; n<m \right \}$ $L_{2} = \left \{ a^{m^{n}}| m,n \geq 1; n<m \right \}$ Which of them are regular? Both L1 and L2 Only L2 Only L1 None Ans. A. Both Please explain.
asked Jan 15, 2019 in Theory of Computation MiNiPanda 402 views
0 votes
0 answers
19
2 votes
1 answer
20
If all finite subsets of LL are regular, then LL is regular. If a proper subset of LL is not regular, then LL is not regular. Subsets of finite sets are always regular. Subsets of finite sets are always regular. Every subset of language is regular than L is regular.
asked Dec 28, 2018 in Theory of Computation iarnav 186 views
9 votes
2 answers
22
Let the language $D$ be defined in the binary alphabet $\{0,1\}$ as follows: $D:= \{ w \in \{0,1\}^* \mid \text{ substrings 01 and 10 occur an equal number of times in w} \}$ For example , $101 \in D$ while $1010 \notin D$. Which of the following must ... $D$ is regular $D$ is context-free but not regular $D$ is decidable but not context-free $D$ is decidable but not in NP $D$ is undecidable
asked Dec 18, 2018 in Theory of Computation Arjun 961 views
...