# Recent questions tagged identify-class-language

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$
2
If every string of a language can be determined, whether it is legal or illegal in finite time, the language is called decidable undecidable interpretive non-deterministic
3
The defining language for developing a formalism in which language definitions can be stated, is called syntactic meta language decidable language intermediate language high level language
4
A finite automaton accepts which type of language : Type $0$ Type $1$ Type $2$ Type $3$
1 vote
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.
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
1 vote
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$
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.
9
$L=\{wxyw|w,x,y\in (a+b)^+ \}$ $L$ is ? Regular Deterministic CFL Non-deterministic CFL CSL
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
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.
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
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!
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.
15
$L = \left \{ x^{l}y^{m}z^{n} | \ l+m+n\ is\ divisible\ by\ 5\right \}$ Is it regular or CFL or CSL ?
16
please tell me if i am wrong
1 vote
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.
18
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
20
L={a^m b^n | m-n=even} Is this language a regular language?
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?
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.