# Recent questions tagged identify-class-language

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)$
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$
1 vote
3
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
4
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
5
A finite automaton accepts which type of language : Type $0$ Type $1$ Type $2$ Type $3$
1 vote
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.
1 vote
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
1 vote
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$
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.
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
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.
1 vote
12
$L=\{wxyw|w,x,y\in (a+b)^+ \}$ $L$ is ? Regular Deterministic CFL Non-deterministic CFL CSL
1 vote
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
1 vote
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.
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
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!
1 vote
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.
1 vote
18
$L = \left \{ x^{l}y^{m}z^{n} | \ l+m+n\ is\ divisible\ by\ 5\right \}$ Is it regular or CFL or CSL ?
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