27
A deterministic finite automaton can only go to infinite loop if the input string is infinite. For finite inputs, the automaton stops when the input string ends. For infinite inputs, for example the automaton for regex 0*1 will loop infinitely if the input string is an infinite sequence of 0.
13
The DFA performs a single state transition on each read input symbol, reads each symbol of the input exactly once, and halts when the input string is exhausted. In order for an infinite loop of state transitions to happen, the input string has to be infinite. DFAs are usually defined for finite inputs only, as the automaton's output is defined by what state ...
3
$A_1$ is regular, since regular languages are closed under intersection and complement, and $A_1 = A \setminus B^{R} = A \cap (B^{R})^{c}$. To show that the reverse $B^{R} = \{x^{R} : x \in B\}$ of a regular language $B$ is regular, take some deterministic finite state machine $M$ with language $B$. Construct a new nondeterministic finite state machine $M'$ ...
2
What you write is a snippet out of a recursive descent parser, one way of writing a program that parses a context free language. It is modelled on a PDA, specifically a LL(1) one. The stack is implicit in the recursive calls your parser does. Recursive descent is popular as it easy to write by hand (some tricks are needed to handle ambiguous constructs, like ...
2
This is one of those trap questions where $L_2$ can actually be written in a different way that makes it obvious that it is a regular language. See if you can figure out what $L_2$ is "really doing", and the answer will become obvious.
Solution:
2
The answer is no. Some context-free languages are inherently ambiguous: every context-free grammar defining a language of this kind will be ambiguous. An example is
$$\{a^ib^jc^k \mid i = j \text{ or } j = k\}$$
2
I think the PDA would stuck as to accept the input string "abcd", the complete input string needs to be read. But your PDA will work only till 'c' is read and get stuck when it finds another letter 'd', but has no transition state.
1
Both HP and MP are decision problems, namely sets of instances that you can think of as descriptive strings. For example,
HP is a collection of pairs $M, x$ where $M$ is the description of a Turing Machine (think of a listing) and $x$ is an input to that machine. An instance is such a pair and a pair is in the set HP if the machine described by $M$ ...
1
I think that you are having trouble distinguishing the difference between regular and non-regular languages, so I try to give a short explanation before I give you an example.
We call a language $L$ regular if it can be decided if a word is in the language with
an algorithm/a machine with constant (finite) memory by examining all symbols
in the word one ...
1
Let L = a*b. LL is regular ($a^nba^mb$). But the language you are asked to check is $a^nba^nb$ where the two n’s are the same. There are plenty of proofs in the last days here that you can adapt. And Myhill-Nerode is super easy.
1
No, in general. If $\bar{L_2}$ and $L_4$ are both the empty language, or have an empty intersection, then $L_4\cap\bar{L_2}\cap\bar{L_1}$ is regular, but that says nothing about whether $L_1$ is regular.
1
Have a good look to the answer you link to. It specifies the language that is generated using two numbers $k,\ell$. These numbers guarantee that the two parts are different without ever knowing where the middle of the string exctly was. I will try to explain.
We have to find (or better, guess) a position in $x$ such that the same position in $y$ carries ...
1
There is a big difference between $\{ xy ∣ |x| = |y|, x = y \}$ and $\{ xy ∣ |x| = |y|, x \ne y \}$. In the first one, we need every symbol in $x$ to be the same as the corresponding symbol in $y$. For inequality, it suffices that at least one symbol in x be different from the corresponding symbol in $y$. The two cases are not symmetrical.
Checking that ...
1
No. The class of languages recognised by pushdown automata is the class of context-free languages, whereas the class of languages recognised by Turing machines is the class of Turing-recognizable (aka recursively enumerable) languages. All context-free languages are recognisable but the converse does not hold.
1
The first language can be described as the set of words on the alphabet $\{a,b\}$ with an even number of $b$'s.
The second one is not the language of words on the alphabet $\{a,b,c\}$ with an equal number of $b$'s and $c$'s (this condition would define a non-regular language). You could use greybeard's description or say: the language contains the empty ...
Only top voted, non community-wiki answers of a minimum length are eligible
