search
Log In

Recent questions tagged identify-class-language

0 votes
1 answer
1
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 in Theory of Computation jothee 10 views
0 votes
1 answer
2
0 votes
1 answer
3
1 vote
2 answers
5
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 in Theory of Computation Lakshman Patel RJIT 331 views
0 votes
3 answers
6
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 in Theory of Computation Lakshman Patel RJIT 337 views
1 vote
3 answers
7
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 in Theory of Computation Lakshman Patel RJIT 336 views
0 votes
0 answers
8
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 in Theory of Computation jothee 107 views
0 votes
1 answer
9
$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 74 views
0 votes
2 answers
10
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 184 views
0 votes
1 answer
11
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 124 views
0 votes
1 answer
12
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 78 views
3 votes
1 answer
13
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 124 views
0 votes
0 answers
14
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 351 views
0 votes
0 answers
16
1 vote
1 answer
17
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 138 views
6 votes
2 answers
19
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 656 views
0 votes
0 answers
21
For $\text{A, B} \subseteq \Sigma^*,$ define $A/B = \{x \in \Sigma^* | \exists y \in B , xy \in A \}$ If L is a CFL and R is regular, then L/R is Regular CFL but not regular Recursive but not CFL None of the above To solve this problem I am trying ... which we know that are not regular but they are CFL. Hence, $L/R$ is CFL but not Regular. Please advise me that am I thinking in correct way or not?
asked Dec 8, 2018 in Theory of Computation !KARAN 91 views
4 votes
1 answer
22
suppose we define max(L) = $ \{ \; x \;|\; x \in L,(\;\forall y \in \Sigma ^*,(y\neq \lambda )\Rightarrow (xy\notin L)\;\;) \;\}$ let L$_1$ = $ \{ \;a^ib^jc^k\;|\;k ≤i \;or\; k ≤j;where\; i,j,k ≥ 0 \;\}$ and L$_2$ = $ \{ \;a^ib^jc^k\;|\;i,j,k ≥ 0 \;\}$ then ... L$_1$ ) and max( L$_2$ ) are CFL (c) max( L$_1$ ) is CFL but max( L$_2$ ) is not CFL. (d) max( L$_2$ ) is CFL but max( L$_1$ ) is not CFL.
asked Nov 25, 2018 in Theory of Computation Prince Sindhiya 402 views
2 votes
0 answers
23
in this question L2 is regular and in first statement what i got that it is DCFL.COMPLEMENT(DCFL).regular and in 2 one DCFLunion regular 3 i am not getting , what i want that can anyone explain the properties of regular with nonregular or anylanguage with regular for this question
asked Nov 25, 2018 in Theory of Computation Prince Sindhiya 83 views
...